Combination - MathsTips.com

A combination is a grouping or selection of all or part of a number of things without reference to the arrangement of the things selected. Thus, the combinations of the three letters a, b, c taken 2 at a time are ab, ac, bc. Note that ab and ba are 1 combination but 2 permutations of the letters a, b.

The symbol $^n C _r$ represents the number of combinations (selections, groups) of n different things taken r at a time. Thus $^9 C _4$ denotes the number of combinations of 9 different things taken 4 at a time.

Note: The symbol C(n, r) having the same meanings as $^n C _r$ is something used.

Difference between Permutation & Combination

In combination only a group is made and the order in which the objects are arranged is immaterial.

On the other hand, in a permutation, not only a group is formed, but also an arrangement in a definite order is considered.

Example:

ab and ba are two different permutations, but each represents the same combination.
abc, acb, bac, bca, cab, cba are six different permutations but each one of them represents the same combination, namely a group of three objects a, b and c.

Note: We use the word ‘arrangements’ for permutations and ‘selections’ for combinations.

Combination Evaluation

Number of combinations of n different things taken r at a time:

$^n C _r = \dfrac{^n P _r}{r!} = \dfrac{n!}{r!(n-r)!} = \dfrac{n(n-1)(n-2) ... (n-r+1)}{r!}$

Example: The number of handshakes that may be exchanged among a partly of 12 students if each student shakes hands once with each other student is:

$^{12} C _2 = \dfrac{12!}{2!(12-2)!} = \dfrac{12 \times 11}{1 \times 2} = 66$

Complementary combination

The following formula is very useful in simplifying calculations:

$^n C _r = ^n C _{n-r}$ (Complementary combination)

This formula indicates that the number of selections of r out of n things is the same as the number of selections of n – r out of n things. Like given in the following cases:

$^5 C _1 = \dfrac{5}{1} = 5$

$^5 C _2 = \dfrac{5 \times 4}{1 \times 2} = 10$

$^5 C _3 = \dfrac{5!}{5!} = 1$

$^9 C _7 = \dfrac{9 \times 8}{2} = 36$

Example: In how many ways a hockey team of eleven can be elected from 16 players?

Solution: Total number of ways $= ^{16} C _{11} = \dfrac{16!}{11! \times 5!} = 4368$

Combination formulas

Formula 1: Number of combinations of n different things taken r at a time in which p particular things will always occur is $^{n-p}C _{(r-p)}$ .

Formula 2: Number of combinations of n dissimilar things taken ‘r’ at a time in which ‘p’ particular things will never occur is $^{n-p}C _{r}$

Example: In a class of 25 students, find the total number of ways to select two representatives, if a particular person will never be selected.

Solution: Total students (n) = 25

A particular students will not be selected (p) = 1,

So total number of ways = $^{25-1}C _2 = ^{24}C _2 = 276$

Formula 3: $^{n}C _{r} + ^{n}C _{(r-1)} = ^{n+1}C _{r}$

Proof:

$^{n}C _{r} + ^{n}C _{(r-1)} = ^{n+1}C _{r}$

$= \dfrac{n!}{r!(n-r)!} + \dfrac{n!}{(r-1)!(n-r+1)!}$

$= \dfrac{n!}{r(r-1)!(n-r)!} + \dfrac{n!}{(r-1)!(n-r+1)(n-r)!}$

$= \dfrac{n!}{(r-1)!(n-r)!} \times ( \dfrac{1}{r} + \dfrac{1}{n-r+1} )$

$= \dfrac{n!}{(r-1)!(n-r)!} \times ( \dfrac{n-r+1+r}{r(n-r+1)} )$

$= \dfrac{n!}{(r-1)!(n-r)!} \times ( \dfrac{n+1}{r(n-r+1)} )$

$= \dfrac{(n+1)n!}{r(r-1)! \times (n-r+1)(n-r)!}$

$= \dfrac{(n+1)!}{r! \times (n+1-r)!}$

$= ^{n+1}C _{r}$

Evaluate $^5 C _3 + ^5 C _2$
Solution: $^5 C _3 + ^5 C _2$
$= ^5 C _3 + ^5 C _{(3-1)}$
$= ^6 C _3 = 20$

Formula 4: $^n C _0 + ^n C _1 + ^n C _2 + ^n C _3 + ... ^nC_n = 2^n$

Formula 5: The number of ways in which (m + n) things can be divided into two groups containing m & n things respectively = $^{(m+n)}C_n = \dfrac{(m+n)!}{m!n!} = ^{(m+n)}C_m$

Example: The number of ways of dividing 3 boys & 2 girls respectively, into groups of 3 & 2 are, as follows:

Group with 3 alphabets	Group with 2 alphabets
ABC	DE
ABD	CE
ACD	BE
BCD	AE
ABE	DC
ACE	BD
BCE	AD
ADE	BC
BDE	AC
CDE	AB

Example: In how many ways we can make two groups of 8 & 3 students out of total 11 students.

Solution: Total students (m + n) = 11

So total number of ways = $^{11}C _8 = \dfrac{11!}{(8! \times 3!)} = 165$

Formula 6: If 2m things are to be divided into two groups, each containing m things, the number of ways = $\dfrac{(2m)!}{(2(m!)^2}$

Example: If we divided 4 alphabets A, B, C & D into two groups containing 2 alphabets, the numbers of ways are 3. The arrangements are shown as below:

I	II
AB	CD
AC	BD
AD	BC

Formula 7: The number of ways to divide n things into different groups, one containing p things, another q thing and so on = $\dfrac{(p+q+r+ ...)!}{(p!q!r! ...)}$ where {n = p + q + r + …}

Formula 8: Total number of combinations of n dissimilar things taken some or all at a time = $2^n-1$ .

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

Solution: We have 32 places for teeth. For each place we have two choice either there is a tooth or there is no tooth. Therefore the number of ways to fill up these places is 232. As there is no person without a tooth, then the maximum population is $2^{32} -1$ .

Formula 9: Total number of combination of n things, taken some or all at a time, when p of them are alike of one kind, q of them are alike of another kind and so on is: {(p+1)(q+1)(r+1)…} – 1, where n=p+q+r+…

Example: Find the total number of combinations of 5 alphabets A, B, A, B, B, taking some or all at a time.

Solution: Here A is twice & B is thrice, so by formula, total combinations = (2+1)(3+1) – 1 = 11

The combinations are as follows:

	Combinations			Total
1 at a time	A	B		2
2 at a time	AA	AB	BB	3
3 at a time	AAB	ABB	BBB	3
4 at a time	AABB	ABBB		2
5 at a time	AABBB			1
Total				11

Exercise

1. In how many ways can 3 women be selected out of 15 women; if one particular woman is always included and two particular women are always excluded?

2. The expression $\dfrac{n!}{2!(n-2)!}$ would be represented by

C(n, n)
C(n,2)
C(n-2,2)
C(n-2,0)

3. Which of the below expression would be equal to C (n,0)

C(n, 1)
C(n, n/2)
C(n, n-1)
C(n, n)

4. In how many ways can a person choose 1 or more out of 4 electrical appliances?

5. Which of the below expression would be equal to C (n, r)

C(n, 0)
C(n, n-r)
C(n, n)
C(n, n/2)

6. C(n,0)+C(n,1)+ C(n,2) + C(n,3) + … + C(n, n) equals

$2^n (n+2)$
$2^n$
$2^{n+1}$
$2^{n-1}$

7. C(n,1)+ C(n,2) + C(n,3) + … + C(n, n) equals

$2^n -1$
$2^n$
$2^{n-1}$
$n2^{n-1}$

8. In a college examination, a candidate is required to answer 6 out of 10 questions which are divided into two sections each containing 5 questions. Further the candidate is not permitted to attempt more than 4 question from either of the section. The number of ways in which he can make up a choice of 6 questions is:

9. C(2n+1,0) + C(2n+1,1) + C(2n+1, 2) + … + C(2n+1,n) equals

$n2^{n}$
$n2^{2n}$
$n2^{2n-1}$
$n2^{2n+1}$

10.C(n,0) + C(n,2) + C(n, 4) + … equal

$2^{n}$
$2^{n+1}$
$2^{n-1}$
$2^{2n+1}$

11. C(n,1) + C(n,3) + C(n, 5) + … equal

$2^{2n}$
$2^{n-1}$
$2^{n}$
$2^{n+1}$

12. In how many ways can 12 books be divided among 3 students so that each receives 4 books?

36540
34650
35640
34560

13. C(n,1) + 2C(n,2) + 3C(n,3) + … + nC(n,n) equals

$n2^{2n}$
$n2^{n-1}$
$n2^{n}$
$n2^{n+1}$

14. C(n,0)+2C(n,1)+3C(n,2) + … + (n+1)C(n,0) equals

$2^{n}$
$n2^{n}$
$2^{n-1}(n+2)$
$n2^{n-1}$

15. Evaluate $^{75} C _{74}$

Comments

Ivan says

March 2, 2017 at 4:54 pm

In the topic “Combination Evaluation” I found that that what you show “[n(n-1)(n-2)…(n-r+a)]/n!” is wrong because [n(n-1)(n-2)…(n-r+a)] < n! so the [n(n-1)(n-2)…(n-r+a)]/n! = 1

Sony says

August 22, 2017 at 4:55 pm

Can you explain about Total number of combination of n things, taken some or all at a time, when p of them are alike of one kind, q of them are alike of another kind and so on is: {(p+1)(q+1)(r+1)…} – 1, where n=p+q+r+…