Restricted Selection and Arrangement

(a) The number of ways in which r objects can be selected form n different objects if k particular objects are

        (i) Always included = ^n-kC_r-k.

        (ii) Never included = ^n-kC_r.

(b) The number of arrangement of n distinct objects taken r at a time so that k particular objects are

        (i) Always included = ^n-kC_r-k.r!,

        (ii) Never included = ^n-kC_r.r!.

Illustration:

A delegation of four students is to be selected form a total of 12 students. In how many ways can the delegation be selected if

(a) All the students are equally willing.

(b) Two particular students have to be included in the delegation.

(c) Two particular students do not wish to be together in the delegation.

(d) Two particular students wish to be included together only,

(e) 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 = ¹²C₄ = 495.

(b) Two particular students are already selected. Hence we need to select 2 out of the remaining 10. Hence the number of  ways = ¹⁰C₂ = 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 this selection can be made = 45.

or

(ii) both are selected. In this case all the four students are selected from the rest of ten students.

This can be done in ¹⁰C₄ = 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 selection = ⁸C₁ = 8

For (ii) the number of ways selection = ⁸C₁ = 8

For (iii) the number of ways selection = ⁸C₂ = 28

For (iv) the number of ways selection = ⁸C₃ = 56

For (v) the number of ways selection = ⁸C₃ = 56

For (vi) the number of ways selection = ⁸C₄ = 70

Hence, total number of ways = 8 + 8 + 28 + 56 + 56 + 70 = 226.

Some results related to ⁿC_r

(i) ⁿC_r = ⁿC_n-r

(ii) If ⁿC_r = ⁿC_k, then r = k or n-r = k

(iii) ⁿC_r + ⁿC_r-1 = ⁿ⁺¹C_r

(iv) ⁿC_r = n/r  ^n-1C_r-1

^(v)  

(vi) (a) If n is even ⁿC_r is greatest for r = n/2

      (b) If n is odd, is greatest for r = (n-1)/2,(n+1)/2