Combinations - Some important results
- If out of n different things, any number of items can be chosen, it can
be done in nC0 +nC1 +nC2
+... +nCn ways. Alternatively, any of n items may or
may not be chosen. Hence number of selections = 2×2×...n times = 2n
=> nC0 +nC1 +... +nCn
= 2n.
It can be shown that nC0 +nC2 +nC4
+... = nC1 +nC3 +nC4
+... = 2n-1.
- Out of n different things, at least one (or more) can be chosen in 2n
-1 ways.
- Number of combinations of n different things taken r at a time when p
particular things always occur is n -pCr -p. Number of
permutations of these is n -pCr -p.r!
- Number of combinations of n different things taken r at a time when p
particular things never occur is n-pCr. Number of
permutations of these is n -pCr.r!
- The number of ways in which m +n different things can be divided into two
groups containing m and n things respectively is (m +n)!/[m!n!]. The reason
is that whenever you choose a group of m out of m +n, a group of n is
automatically left behind. Number of combinations of m +n things taken m at a
time is
n +mCm = (m +n)!/[m! (m +n -1)!] = (m + n)!/[m! n!]
- If subgroups are equal i.e. n = m, then 2m things can be divided into two
groups of m each in (2m)!/(m!)² ways. If you distribute things to two
persons, then this formula gives number of subdivisions. If it is possible to
interchange the two groups then number of divisions is (2m)!/[(m!)².2!]
- Number of division of m +n +p things into groups of m, n, p things
respectively is (m +n +p)!/[m!.n!.p!]
- If 3m things are divided into 3 equal groups, then number of divisions is
(3m)!/(m!)³ and if the groups are interchangeable, the number of divisions is
(3m)!/[(m!)³.3!]
- If there are p +q +r things, where p things are alike, q things are alike
and r things are alike, a non-empty selection can be made in (p +1)(q +1)(r +1) -1
ways as 0, 1, 2, ..., p items of p may be chosen; 0, 1, 2, ..., q
items of q may be chosen etc.
- If there are p +q +r things, where p things are alike, q things are alike
and remaining r are all different, then a non-empty selection can be made in
(p +1)(q +1). 2r -1 ways. (Prove it!)
Illustrative Examples
Example
In how many ways can final eleven be selected from 15 cricket players if
- there is no restriction
- one of them must be included
- one of them, who is in bad form, must always be excluded
- two of them being leg spinners, one and only one leg spinner must be included?
Solution
- 11 players can be selected out of 15 in 15C11 ways
= 15C4 = (15.14.13.12) / (1.2.3.4) = 1365 ways.
- Since a particular player must be included, we have to select 10 more out
of remaining 14 players. This can be done in
14C10 = 14C4 = (14.13.12.11)/(1.2.3.4) = 1001 ways.
- Since a particular player must be always excluded, we have to choose 11
players out of remaining 14. This can be done in
14C11 ways = 14C3 = (14.13.12)/(1.2.3) = 364 ways.
- One leg spinner can be chosen out of 2 in² C1 = 2 ways. Then
we have to select 10 more players out of 13 (because second leg spinner can't
be included). This can be done in
13C10 ways = 13C3 = (13.12.11)/(1.2.3) = 286 ways.
Thus required number of combinations = 2×286 = 572
Example
Out of 5 boys and 4 girls, a committee of 5 is to be formed so as to
include no more than 2 girls. In how many ways can it be done?
Solution
We may choose 5 boys and no girl in 5C5.4C0
= 1×1 = 1 way only.
We may choose 4 boys and 1 girl in 5C4 .4C1
= 5C1.4C1 = 5×4 = 20 ways.
We may choose 3 boys and 2 girls in 5C3.4C2
= 10×6 = 60 ways.
Hence required number of combinations = 1 +20 +60 = 81.
Example
- Find the number of ways in which 18 different objects can be divided into
three groups each containing 6 objects.
- Find the number of ways in which 18 different objects can be distributed equally among 3 persons.
Solution
- If 18 different objects are to be divided into 3 groups of 6 each and the
order of groups is not important, number of ways of doing so = 18!/[(6!)³.3!]
- If 18 different objects are to be distributed 6 each to 3 persons, it can
be done in 18!/(6!)³ ways.
Example
There are 15 points in a plane, no three of which are in the same straight
line except 4 which are collinear. Find the number of
- straight lines
- triangles formed by joining them.
Solution
- If no three points out of 15 points lie on a line, then the number of
lines is 15C2 as exactly one line is drawn through two
points. Since 4 out of 15 points are collinear, they from only one line
instead of 4C2 lines. Hence the number of lines
gets decreased by 4C2 -1. Hence the required number of lines
= 15C2 -(4C2 -1) = 105 -6 +1 = 100
- A triangle is formed by joining 3 non-collinear points. So if the 15
points are all non-collinear, 15C3 triangles can be
formed. But here 4 points lie on a line and form no triangle instead of
4C3. Thus the required number of triangles
= 15C3 -4C3 = 455 -4 = 451
Example
Find the number of (i) combinations (ii) permutations of four letters taken
from the word EXAMINATION.
Solution
The word examination consists of 11 letters -
(AA), (II), (NN), E, X, M, T, O.
The following combinations are possible:
(a) 2 alike, 2 alike:³C2 = 3 ways
(b) 2 alike, 2 different:³C1×7C2 = 63 ways
(c) all 4 different: 8C4 = 70 ways
Hence required number of combinations = 3 +63 +70 = 136.
To find the number of permutations:
In (a), the number of permutations = 3×4!/[2!2!] = 18
In (b), the number of permutations = 63×4!/2! = 756
In (c), the number of permutations = 70×4!= 1680
Hence required number of permutations = 18 +756 +1680 = 2454.
Exercise
- A roller coaster has 3 seats and 4 children want to ride. How many ride
combinations are possible? (Make an impossible assumption that little
children don't fight over who sits where!)
- A baseball team has 13 members. How many lineups of 9 players are
possible? The position of each member in the lineup is not important.
- In an examination, a candidate is required to answer 6 out of 10
questions which are divided into two groups, each containing 5 questions, and
he is not permitted to attempt more than 4 questions from each group. In how
many ways can he make up his choice?
- A box contains two white balls, three black balls and four red balls. In
how many ways can three balls be drawn from the box if at least one black
ball is to be included in the draw?
- Out of 3 books on Economics, 4 books on Political Science and 5 books on
Geography, how many collections can be made if each collection consists of
(i) exactly one book on each subject (ii) at least one book on each subject?
- Find the number of three digit numbers (repetitions allowed) such that at
least one of the digits is 9.
- A committee of 6 is chosen from 10 men and 7 women so as to contain at
least 3 men and 2 women. In how many different ways can it be done if two
particular women refuse to serve on the same committee?
- There are 6 boys and 3 girls in a class. A committee of 5 is to be
selected such that 3 boys and 2 girls are on the committee.
(i) In how many ways can the committee be selected?
(ii) What is the number of ways if there is at least one girl on the committee?
- In how many ways can a lawn-tennis mixed doubles be made up from 7
married couples if no husband and wife play in the same set?
- In how many ways can a pack of 52 cards be divided equally among 4 players in order?
- Determine the number of ways of obtaining 4 heads and 2 tails in 6 tosses of a coin.
- From 4 mangoes, 5 oranges and 6 apples, how many selections can be made
by taking at least anyone of them?
- A committee of 6 is to be formed from 6 boys and 4 girls. In how many
ways can this be done if the committee contains (i) 2 girls (ii) at least two girls?
- A man has six friends. In how many ways can he invite one or more of them to a tea party?
- How many even numbers are there with three digits such that if 5 is one
of the digits, then 7 is the next digit?
- Find the number of ways in which 5 white balls and 4 black balls can be
arranged in a row so that no two black balls are together.
- Everybody in a room shakes hands with everybody else. The total number of
handshakes is 66. How many people are there in the room?
- At a party, each person shook hands with everyone else. Mr. Lee shook
hands with 3 times as many men as women. Mrs Lee shook hands with 4 times as
many men as women. How many men and women were there at the party?
- (i) There are 12 points in a plane of which 5 are collinear. These points
are joined in pairs. Find the number of straight lines formed.
(ii) How many triangles can be formed by joining the vertices of a hexagon?
- How many diagonals are there in a polygon with n sides?
- How many words can be formed by taking 4 letters at a time out of the letters of the word
(i) MATHEMATICS
(ii) EXAMINATION
Answers
1. 4
2. 715
3. 200
4. 6
5. (i) 60
(ii) 3255
6. 252
7. 7800
8. (i) 60
(ii) 120
9. 420
10. 52!/(13!)4
11. 15
12. 209
13. (i) 90 (ii) 185
14. 63
15. 365
16. 15
17. 12
18. 16 men, 5 women
19. (i) 57 (ii) 20
20. [n (n -3)]/2
21. (i) 2454 (ii) 2454