Restricted selection
Arrangement
(a) The number
of ways in which r objects can be selected from n different objects if k
particular objects are
(i)
always
included = n-k Cr-k
(ii) never included = n-k
Cr
(b) The
number of arrangements of n distinct objects taken r at a time so that k
particular objects are
(i)
always
included = n-k Cr-k .r!.
(ii) never included = n-k Cr .r!.
(c) The number of combinations of n
objects, of which p are identical, taken r at a time is
= n-pCr + n-pCr-1
+ n-pCr-2+ …… + n-pC0 if r £ p and it is:
= n-pCr + n-pCr-1
+ n-pCr -2+ ……+ n-pCr-p if r > p
Example.1
A delegation of four students is to be selected from a
total of 12 students. In how many ways can the delegation be selected .
(a) If all the students are equally willing.
(b) If two particular students have to be included in
the delegation.
(c) If two particular students do not wish to be
together in the delegation.
(d) If two particular students wish to be included
together only.
(e) If two particular students refuse to be together and
two other particular student wish to be together only in the delegation.
Solution
(a) Formation of delegation means selection of 4 out of
12. Hence the number of ways = 12C4 = 495.
(b)
If two particular students are already selected. Here we need to select only 2
out of the remaining 10. Hence the number of ways = 10C2
= 45.
(c) The number of
ways in which both are selected = 45. Hence the number of ways in which the two
are not included together
= 495 – 45 = 450.
(d)
There are two possible cases
(i) Either both are selected. In this case, the number
of ways in which the selection can be made = 45.
(ii) Or both are not selected. In this case all the four
students are selected from the remaining ten students.
This can be done in 10C4 = 210
ways.
Hence the total number of ways of selection = 45 + 210
= 255.
(e)
We assume that students A and B wish to be selected together and students C and
D do not wish to be together. Now there are following 6 cases.
(i)
(A, B, C) selected, (D) not selected
(ii) (A, B, D) selected (C) not selected
(iii) (A, B) selected (C, D) not
selected
(iv) (C) selected (A, B, D) not
selected
(v) (D) selected (A, B, C) not
selected
(vi) A, B, C, D not selected
For (i) the number of ways of selection = 8C1
= 8
For (ii) the number of ways of selection = 8C1
= 8
For (iii) the number of ways of selection = 8C2
= 28
For (iv) the number of ways of selection = 8C3
= 56
For (v) the number of ways of selection = 8C3
= 56
For (vi) the number of ways of selection = 8C4
= 70
Hence total number of ways = 8 + 8 + 28 + 56 + 56 + 70
= 226.
Some results related to nCr
(I) nCr
= nCn-r
(ii) If nCr
= nCk , then r = k or n-r =k
(iii) nCr + nCr-1
= n+1Cr
(iv) nCr = 
n-1Cr-1
(v) 
(vi) (a) If n is even ,
nCr is greatest for r = n/2
(b)
If n is odd, nCr is greatest for r = 
, 
Example.2
How
many triangles can be formed by joining the vertices of an n- sided polygon. How
many of these triangles have .
(i)
exactly one side common with that of the polygon
(ii) exactly two sides common with that of the polygon
(iii) no sides common with that of the polygon
Solution
Number of triangles formed by joining the vertices of
the polygon
= number of selections of 3 points from n points =nC3
=
.
Let the vertices of the polygon be marked as
A1, A2,A3,…. An.
(1) Select two
consecutive vertices A1, A2 of the polygon. For the
required triangle, we can select the third vertex from the points A4,A5,…..
An-1. This can be done in n-4C1 ways. Also two
consecutive points (end points of a side of polygon) can be selected in n ways
. Hence the total number of required triangles = n.n-4C1 =
n(n – 4).
(2) For the required
triangle, we have to select three consecutive vertices of the polygon. i.e. (A1
A2 A3), (A2 A3 A4), (A3
A4 A5), …. ,(An A1 A2).
This can be done in n ways.
(3)
Triangles
having no side common + triangles having exactly one side common + triangles
having exactly two sides common (with those of the polygon) = Total number of
triangles formed
&⇒ Triangles having no side common with
those of the polygon
= nC3
– n(n-4) –n = 
-n(n-4)
–n
= 
= 
= 
.
