Combinations

Combinations are selection of items from a group of items where the order of selection does not matter. Contrary to permutations which deals with arranging those items/objects in definite order.

Counting problems in the mathematical field known as combinatorics. In simple words, combinations deals with selection while permutations deals with arrangement of objects without actually listing them. In combinations, we can select items in any order. In this article we come across basic principles of counting, combinations formula, permutation and combination and solved examples.

Basic Principles of Counting

Two basic principles of counting are:

1. Fundamental principle of counting: Let the event X occurs in n different ways and another event Y occurs in m different ways. The total number of occurrences of two events is = m x n.

2. Addition principle: Let event X occurs in m different ways and event Y occurs in n different ways and both the event cannot occur together, occurrence of events X or Y is m + n.

Permutation and Combinations Formulas

Permutation: Arrangement of objects in a definite sequence or order and the order of arrangement matters.

Number of permutation of n objects taken n at time is

nPn = n!

Number of permutation of n objects taken r at time is

nPr=n!(nr)!^nP_r = \frac{n!}{(n-r)!}

Combinations: Selection of objects from a group of objects where the order of selection does not matter.

Combinations Formula

Selection of r objects from n objects is given by:

nCr=n!r!(nr)!^nC_r = \frac{n!}{r!(n-r)!}

Important results

1.nCn=n!n!  0!=1^nC_n = \frac{n!}{n!\; 0!} = 1

2.The number of combinations of n different items taken nothing at all is considered as 1. Counting combinations is counting the number of ways in which all or some of the objects are selected at a time. Selecting no item is the same as leaving behind all the objects . There is only one way of doing that. Thus we define nC0=1^nC_0 =1

3.nCr=n!r!  (nr)!^nC_r =\frac{n!}{r!\; (n-r)!} , 0 ≤ r ≤ n

4.nCnr=n!(nr)!  (n(nr))!=n!(nr)!  r!=  nCr^nC_{n-r}=\frac{n!}{(n-r)!\; (n-(n-r))!}= \frac{n!}{(n-r)!\; r!} = \; ^nC_{r}

5.nCa=  nCb^nC_{a}= \; ^nC_{b}

⇒ a = b or a = n-b 

I.e., n = a+b

6.nCr+nCr1=  n+1Cr^nC_{r}+^nC_{r-1}= \; ^{n+1}C_{r}

Related articles:

Permutations and combinations

Binomial theorem

Problems on Permutations and combinations 

How to Calculate the Probability of Combinations

Let us understand the concept with the help of some of the examples:

Example 1:

a) In how many ways can you allot 5 beds to 3 people?

b) In how many ways can the letters of the word ‘MOBILE’ be arranged?

c) How many four digit numbers can be formed with digits 5, 6, 7 and 9 and with distinct digits?

Solution:

a) First person can choose any one bed among the 5 beds available. Similarly 2nd person will be left with 4 choices and 3rd will be having 3 choices.

Number of ways of allotting = 5 x 4 x 3 = 60 ways

b) Letters of the word ‘MOBILE’ can be arranged in 5! Ways i.e.120 ways.

c) Number of distinct ways of forming 4 digit numbers with distinct digits is 4!, which is 24 words.

Example 2: There are 10 points out of which 3 are collinear. Find

a) How many lines can be formed from by using these points?

b) How many triangles can be formed using these points?

Solution:

a) Since to form one line two points are required. Let’s suppose all the points are non-collinear, the number of lines formed using these points will be 10C2 .

And the number of lines formed using collinear points will be 3C2.

Therefore, the number of lines formed will be 10C23C2 + 1 (where 1 is for the one line that is being formed using those 3 points).

b) Number of triangles formed if all the 10 points are non-collinear will be 10C3.

Number of triangles formed using 3 non-collinear lines 3C3.

Hence the number of triangles formed when out 10 points 3 are collinear will be 10C3 3C3.

Example 3: In a locality there are 87 families, among which 52 families have at most 2 children. In an annual locality quiz competition 20 families are chosen to participate, of which 18 families have at most 2 children. In how many can the choice be made.

Solution: Since the 20 families are to be selected out of which at least 18 families have at most 2 children. Therefore there are three possible combinations

i. 18 – Family (At most 2 child) and 2 – Family (Other)

ii. 19 – Family(At most 2 child) and 1 – Family(Other)

iii. 20 – Family (At most 2 child).

Therefore the possible ways of making the choice is = 52C18 x 35C2 + 52C19 x 35C1 + 52C20 .

De-arrangement: It can be defined as the permutation arrangement of elements of a certain in such a way that no element of that set appears in original positions. It is given by the formula given below.

Dn = n! (111!+12!13!+14!15!+.1n!)(1 – \frac{1}{1!} + \frac{1}{2!} – \frac{1}{3!} + \frac{1}{4!} – \frac{1}{5!} + ….\frac{1}{n!})

Let us have a look into the below solved example to have a clear idea.

Example: In how many can you put 9 letters in respective envelopes such that exactly 4 go into the correct address?

Solution: Number of selecting 4 correct envelopes are 9C4 i.e. 126..

Derangement of remaining 5 envelopes is D5 = 44.

Hence the total number of ways of arrangement = 44 x 126 = 5544.

Problems on Combination

Example 1: In how many ways 5 boys can be arranged in a queue such that

a) Two particular boys of them are always together

b) Two particular boys of them are never together

Solution:

a) If two boys are always together, then they will be treated as one entity. Hence it can be arranged in 4! ways. Again two as one entity can also arrange among themselves in 2 ways.

Therefore required arrangement = 4! x 2 = 24 x 2 = 48 ways.

b) Among the 5 boys total number of permutation will be = 5! = 120.

The arrangement in which two boys are always together is 48 ways.

The remaining in no two boys are never together will be = 120 – 48 = 72 ways.

Example 2: How many combinations can be made up of 4 birds, 5 amphibians and 3 reptiles so that each combination has birds, amphibians and reptiles?

Solution: Since it asks the case of number of combinations i.e atleast 1 of each category among birds, amphibians and reptiles.

So combination of birds is given by 24 – 1.

Similarly, the combination of amphibians is given by = 25 – 1.

So the combination of reptiles is 23-1.

Therefore, the total combination at least one of each category will be = (24-1) x (25-1) x (23-1) = 3255.

Example 3: How many different (1) combination (2) permutation can be made by using four letters of the word “COMBINATION”.

Solution:

1. Since in the word “COMBINATION” there are 2O, 2I and 2N. Hence, there are 8

distinct words in letters.

For combination selection has to be made. 4 letter words can be selected in 3 different

ways which are :-

i) All 4 are different letters: There are 8 distinct letters hence selection can be made in = 8C4 = 70

ii) 2 are same letters and 2 are different letters: There are 3 pairs of two same letters from which 1 pair has to be selected and the remaining two are selected from 7 remaining.

Thus selection can be made in = 3C1 x 7C3 = 63.

iii) 2 are same and other 2 are also same letters: From the three pairs selection of two pairs has to be made i.e 3C2 = 3.

Total combinations: = 70 + 63 + 3 = 136.

2. Now permutations of these selected 4 letter words will be again 3 cases:

i) 4 different letters: Selection as well as arrangement of these will be 8C4 x 4! = 1680

ii) 2 are same letters and 2 are different letters = 3C1 x 7C3 x 4!/2! = 756

iii) 2 are same and other 2 are also same letters = 3C2 x 4!/(2! X 2!) = 18.

Therefore, Total permutations: = 1680 + 756 + 18 = 2454.

Example 4: 47C4+5r=152rC3=^{47}{{C}_{4}}+\underset{r=1}{\overset{5}{\mathop{\sum }}}\,{}^{52-r}{{C}_{3}}=

Solution: 

47C4+r=1552rC3=51C3+50C3+49C3+48C3+47C3+47C4=51C3+50C3+49C3+48C3+48C4=51C3+50C3+49C3+49C4[x1+x2+..+x6].^{47}{{C}_{4}}+\sum\limits_{r=1}^{5}{^{52-r}{{C}_{3}}}{{=}^{51}}{{C}_{3}}{{+}^{50}}{{C}_{3}}{{+}^{49}}{{C}_{3}}{{+}^{48}}{{C}_{3}}{{+}^{47}}{{C}_{3}}{{+}^{47}}{{C}_{4}}\\ {{=}^{51}}{{C}_{3}}{{+}^{50}}{{C}_{3}}{{+}^{49}}{{C}_{3}}{{+}^{48}}{{C}_{3}}{{+}^{48}}{{C}_{4}} \\{{=}^{51}}{{C}_{3}}{{+}^{50}}{{C}_{3}}{{+}^{49}}{{C}_{3}}{{+}^{49}}{{C}_{4}} [{{x}_{1}}+{{x}_{2}}+…..+{{x}_{6}}].\\

Example 5: If 2nC3:nC2=44:3,^{2n}{{C}_{3}}:{{\,}^{n}}{{C}_{2}}=44:3,  then for which values of r, the value of nCr^{n}{{C}_{r}} will be 15?

Solution:

(2n) !(2n3) ! . 3 ! times2 !  times(n2) !n ! =443n4(2n1)=442n=12n=6Now 6Cr=156Cr=6C2 or 6C4r=2, 4.\frac{(2n)\ !}{(2n-3)\ !\ .\ 3\ !}\text \ times \frac{2\ !\ \text\ times (n-2)\ !}{n\ !}\ =\frac{44}{3} \\\Rightarrow n \Rightarrow 4(2n-1)=44\\\Rightarrow 2n=12\\\Rightarrow n=6 \\Now \ ^{6}{{C}_{r}}=15 \\\Rightarrow ^{6}{{C}_{r}}{{=}^{6}}{{C}_{2}} \ or \ ^{6}{{C}_{4}}\\\Rightarrow r=2,\ 4.\\

Example 6: In a city no two persons have identical set of teeth and there is no person without a tooth. Also no person has more than 32 teeth. If we disregard the shape and size of tooth and consider only the positioning of the teeth, then what is the maximum population of the city?

Solution:

We have 32 places for teeth. For each place, we have two choices either there is a tooth or there is no tooth. Therefore the number of ways to fill up these places is 2322^{32}. As there is no person without a tooth, the maximum population is 23212^{32}-1.

Example 7: If nC9=nC8^nC_{9}= ^nC_{8} find nC17^nC_{17}

Solution:

Given  nC9=nC8^nC_{9}= ^nC_{8}

I.e, n!9!(n9)!=n!8!(n8)!\frac{n!}{9!(n-9)!} = \frac{n!}{8!(n-8)!}

 1/9 = 1/(n-8)

n-8 = 9

n = 8+9 = 17

Hence nC17=17C17=1^{n}C_{17} = ^{17}C_{17} = 1

Example 8: A class consists of 6 girls and 7 boys. In how many ways can a group of 5 members be selected if the team has (i) no girl (ii) at least 3 girls. 

Solution:

(i)Only boys need to be selected since the team has no girls.

Therefore 5 out of 7 boys can be selected in 7C5^{7}C_{5} ways.

I.e 7!/(5! 2!) = 21

(ii) Since the team has to consist of at least 3 girls, it will consist of 3 girls and 2 boys or 4 girls and 1 boy.

3 girls and 2 boys can be selected in 5C3×7C2^{5}C_{3} \times ^{7}C_{2} ways. 

4 girls and 1 boy can be selected in 5C4×7C1^{5}C_{4} \times ^{7}C_{1} ways. 

So required number = 5C3×7C2^{5}C_{3} \times ^{7}C_{2} + 5C4×7C1^{5}C_{4} \times ^{7}C_{1} = 210+35 = 245