Restricted Combinations

Restricted Combinations:

Restricted combinations refer to a method of counting the number of ways in which a limited or restricted set of items can be combined. For example, suppose you have a set of five objects, and you want to choose three of them. However, there are certain restrictions that limit the possible combinations. Maybe two of the objects are identical and cannot be selected together, or perhaps you must choose at least one item from a particular subset of the set.

Number of combinations of n different things taken any number at a time:

Obviously, there are two possibilities for a particular thing- either it is selected, or it is left out. This is true for each of the n different objects. Now, each way of selecting an object is to be associated with each way of selecting the other things. Hence, the total number of combinations = 2 x 2 x 2 … to n factors = 2ⁿ.

But the total number of combinations calculated as above includes one case in which all the things have been left out which is inadmissible.

Hence, the required number of combinations = 2ⁿ – 1

Total Number of Combinations by taking any number at a time when the things are not all different:

Let there be (p + q + r + …) objects in which p things are alike of one kind, q things are alike of a second kind, r things are alike of a third kind, and so on. We are to find out the total number of combinations of these things taking any number at a time.

Now, p alike things of the first kind can be selected in (p + 1) ways, since one can select 1, 2, 3, … p of them or none at all. Also, for each way of selection of things of the first kind, the second kind of things can be selected in (q + 1) ways. Thus, the total number of combinations of the first and second kinds of things is (p + 1) (q + 1). Similarly, the total number of combinations of p like things of the first kind, q like things of the second kind, and r like things of the third kind is (p + 1) (q + 1) (r + 1). Therefore, the total number of combinations = (p + 1) (q + 1) (r + 1) …, which includes the case in which none of the things has been taken, which is inadmissible.

Hence, the required total number of combinations = { (p + 1) (q + 1) (r + 1) … } – 1

Division into Groups:

(a) Number of ways in which (m + n) different things can be divided into two groups containing m and n things respectively.

Here, m things can be selected out of (m + n) different things in ^m+nC_m ways. For each of these ^m+nC_m selections, the second group can be selected in ⁿC_n ways (as after selecting m things for the first group, there will be n things remaining, all of which are to be included in the second group).

Thus, the required number of selections, ^m+nC_m x ⁿC_n = (m + n)! / (m! n!)

Note: If each of the two groups is to contain an equal number of objects, then the interchange of the group, would not give any new distribution. In that case, the total number of combinations would be (2m!) / [(m!)² (2!)].

But if 2m different objects are distributed equally among two persons, the number of ways would be (2m!) / (m!)² (the reason is obvious because in this case, the interchange of the two sets of objects makes a different distribution since the persons are different).

(b) Total number of ways in which (p + q + r) different things can be divided into three groups containing p, q, and r objects respectively.

Here, p things can be selected out of (p + q + r) different things in ^p+q+rC_p ways. For each of these selections, the second group containing q things can be selected from the remaining q + r objects in ^q+rC_q ways. Also, when the first and the second groups have been selected, the third group containing r things can be selected from the remaining r things in ^rC_r ways.

Note: If each of the three groups contains an equal number of objects i.e. if p = q = r, then the interchange of the three groups will not give any new distribution. As the three groups can be interchanged in 3! ways, the total number of combinations in this case will be reduced by a factor 3!. Hence, the total number of combinations of 3p different objects in three groups equally is (3p)! / [(p!)³ (3!)].

But, if 3p different objects be distributed equally among three persons, then the number of selections, as discussed earlier would be (3p)! / (p!)³.