Module 5

1. Permutations and Combinations

Permutations
1. In how many ways can 6 men and 6 women be seated in a row
(i) if any person may sit next to any other?
(ii) if men and women must occupy alternate seats?
2. Find the number of permutations of the letters of the word MASSASAUGA. In
how many of these, all four A’s are together? How many of them begin with S?
3. (a) How many arrangements are there for all letters in the word
SOCIOLOGICAL?
(b) In how many of these arrangements
(i) A and G are adjacent? (ii) all the vowels are adjacent.
4. Four different mathematics books, five different computer science books and
two different control theory books are to be arranged in a shelf. How many
different arrangements are possible if (a) the books in each particular subject
must all be together? (b) only the mathematics books must be together?

5. How many positive integers n can we form using the digits 3,4,4,5,5,6,7 if we
want n to exceed 5,000,000?

Combinations
6. A certain question paper contains three parts A, B, C with four questions in
part A, five questions in part B and six questions in part C. It is required to
answer seven questions selecting at least two questions from each part. In how
many different ways can a student select his seven questions for answering?
7. A woman has 11 close relatives and she wishes to invite 5 of them to dinner.
In how many ways can she invite them in the following situations?
(i) There is no restriction on the choice.
(ii) Two particular persons will not attend separately.
(iii) Two particular persons will not attend together.

8. (i) A party is attended by n persons. If each person in the party shakes hands
with all the others in the party, find the number of handshakes.

(ii) There are n married couples attending a party. Each person shakes hands with
every person other than his or her spouse. Find the total number of handshakes.

9. (a) How many diagonals are there in a regular polygon with n sides?

(b) Which regular polygon has the same number of diagonals as it sides?
10. Find how many distinct four digit integers one can make from the digits
1,3,3,7,7,8.
2. Binomial theorem and Multinomial theorem
Binomial theorem
11. Obtain the sums of all the coefficients in the expansions of
n
(a) ( x + y )n (b) ( x 1 + x 2+ …+ x k )

Hence obtain the sum of all the coefficients in the expansions of each of the
following

(i) ( x + y )10 (ii) ( x + y + z+ w )5 (iii) ( x +2 y−3 z+ 2u+3 v )12

12. Determine the coefficient of x 9 y 3 in the expansion of ( 2 x−3 y )12

( )
15
2 2
13. Determine the coefficient of x 0 in the expansion of 3 x −
x

14. Determine the coefficient of x 12 in the expansion of x 3 ( 1−2 x )10

15. Determine the coefficient of x k in the expansion of ( 1+ x + x 2 ) ( 1+ x )n, where n is

a positive integer and 0 ≤ k ≤ n+2.

Multinomial theorem

16. Determine the coefficient of xy z2 in the expansion of ( 2 x− y−z )4 .

17. Determine the coefficient of x 2 y 2 z 3 in the expansion of ( 3 x−2 y−4 z )7 .

6
18. Determine the coefficient of x 11 y 4 in the expansion of ( 2 x 3−3 x y 2 + z 2 ) .

19. Determine the coefficient of a 2 b 3 c 2 d 5 in the expansion of ( a+ 2b−3 c +2 d +5 )16 .

10
20. Determine the coefficient of x 21 x 3 x34 x 45 in the expansion of ( x 1 + x 2+ x 3 + x 4 + x 5 ) .

3. Combinations with Repetitions

21. (i) A bag contains coins of seven different denominations, with at least one
dozen coins in each denomination. In how many ways can we select a dozen
coins from the bag?
(ii) Determine the number of distinct terms in the expansion of
16
( x 1 + x 2+ x 3 + x 4 + x 5 ) .
22. (i) In how many ways can we distribute 10 identical marbles among 6 distinct
containers?
(ii) Determine the number of non-negative integer solutions of the equation
x 1+ x2 + x 3 + x 4 + x 5=8
23. (i) A cake shop sells 20 kinds of cakes. If there are at least a dozen cakes of
each kind, in how many ways can a dozen cakes be chosen?
(ii) Determine the number of positive integer solutions of the equation
x 1+ x2 + x 3=17.
24. (i) In how many ways can we distribute 7 apples and 6 oranges among 4
children so that each child gets at least 1 apple?
(ii) Determine the number of non-negative integer solutions of
x 1+ x2 + x 3 + x 4 + x 5=30, where x 1 ≥ 2 , x 2 ≥3 , x 3 ≥ 4 , x 4 ≥ 2 , x5 ≥ 0.
25. In how many ways can 10 identical pencils be distributed among 5 children in
the following cases:
(i) There are no restrictions.
(ii) Each child gets at least one pencil.
(iii) The youngest child gets at least two pencils.
26. In how many ways can one distribute eight identical balls into four distinct
containers, so that (i) no container is left empty? (ii) the fourth container gets an
odd number of balls.
27. A total amount of Rs.1500/- is to be distributed to 3 poor students, A, B, C of
a class. In how many ways can the distribution be made in multiples of Rs.100?
(i) if everyone of these must get at least Rs.300?
(ii) if A must get at least Rs.500, and B and C must get at least Rs.400 each?
28. A total of Rs. 10000 is to be distributed to four people: A, B, C, D in multiples
of Rs. 1000. In how many ways can the distribution be done (i) if there is no
restriction? (ii) if every one of these people should receive at least Rs. 1000? (iii)
if everyone should receive at least Rs.1000 and A should receive at least
Rs.5000?
29. (i) Determine the number of ways of placing 20 identical balls into 5 boxes
with at least one ball put into each box.

(ii) Determine the number of distinct terms in the expansion of ( w + x+ y+ z )10 .

30. (i) Find the number of ways of distributing 7 identical pens

and 7 identical pencils for 5 children so that each gets at least
1 pen and at least 1 pencil.
(ii) Determine the number of non-negative integer
solutions of the equation

x 1+ x2 + x 3 + x 4=7.
4. Rook Polynomials

31. Obtain the rook polynomial for the 3 ×3 board by using the expansion
formula.
32. By using the expansion formula, obtain the rook polynomial for the board C
shown below:
33. By using the expansion formula, Obtainthe rook polynomial for the board C
shown below:
(made up of unshaded parts)

34. Obtain the rook polynomial for the board shown

below (shaded part).

35. A board consists of the shaded part of the following figure. Obtain its rook
polynomial.

36. An apple, a banana, a mango and an orange are to be distributed to four

boys B1 , B2 , B3 , B 4 . The boys B1 and B2 do not wish to have apple, the boy B3
doesn’t want banana or mango and B4 refuses orange. In how many ways can
the distribution be made so that no boy is displeased?

37. Five teachers T 1 , T 2 , T 3 , T 4 ,T 5 are to be made class teachers for five classes,
C 1 , C 2 , C3 , C 4 ,C 5 , one teacher for each class. T 1 and T 2 do not wish to become the
class teachers for C 1 or C 2 , T 3 and T 4 for C 4 or C 5 and T 5 for C 3 or C 4 or C 5. In how
many ways can the teachers be assigned the work (without displeasing any
teacher)?
38. Four persons P1 , P2 , P3 , P4 who arrive late for a dinner party find that only one
chair at each of five tables T 1 , T 2 , T 3 , T 4 and T 5 is vacant. P1 will not sit at T 1 or T 2,
P2 will not sit at T 2 , P3 will not sit at T 3 or T 4 and P4 will not sit at T 4 or T 5 . Find
the number of ways they can occupy the vacant chairs.
39. A girl student has sarees of five different colors: blue, green, red, white and
yellow. On Mondays she doesn’t wear green; on Tuesday’s blue or red; on
Wednesday’s blue or green; on Thursday’s red or yellow; on Friday’s red. In how
many ways can she dress without repeating a color during a week (form Monday
to Friday)?
40. A pair of dice, one red and the other green, is rolled six times. Find the
probability that we obtain all six values on both the red die and the green die
under the restriction that the ordered pairs ( 1 ,1 ) , ( 1 ,5 ) , ( 2 , 4 ) , ( 3 , 6 ) , ( 4 ,2 ) , ( 4 , 4 ) , ( 5 ,1 )
and (5 , 5) do not occur. [Here an ordered pair (a ,b) indicates a on the red die and
b on the green].
5. Generating functions.

41. (i) Find the sequence generated by the function ( 3+ x )3

(ii) Find the generating function for the sequence: 12 ,22 , 32 , 42 , …

42. (i) Find the sequence generated by the function 2 x 2 ( 1−x )−1

(ii) Find the generating function for the sequence: 02 , 12 , 22 ,3 2 , 4 2 ,…

−1
43. (i) Find the sequence generated by the function ( 1+3 x ) 3

(ii) Find the generating function for the sequence: 13 ,23 , 33 , 43 , …

−1
44. (i) Find the sequence generated by the function ( 1−4 x ) 2

(ii) Find the generating function for the sequence: 03 , 13 ,23 , 33 , 43 , …

45. (i) Find the sequence generated by the function 3 x 3+ e2 x

(ii) Find the generating function for the sequence: 1 ,1 , 0 , 1 ,1 , 1 ,…

( 1+ x )4 15
46. Determine the coefficient of x in 4
( 1−x )
3
x −5 x
47. Determine the coefficient of x 10 in
( 1−x )3
1
48. Determine the coefficient of x 8 in
( x−3 ) ( x−2 )2
49. Determine the coefficient of:
5
(i) x 27 in ( x 4 + x 5 + x 6 +… )
 5
(ii) x 18 in ( x + x 2+ x3 + x 4 + x 5 ) ( x 2+ x3 + x 4 + … )

50. Determine the coefficient of:

5
(i) x 27 in ( x 4 +2 x 5 +3 x 6 + … )
3
(ii) x 18 in ( x + x 3+ x5 + x 7 + x 9 ) ( x 3+ 2 x 4 +3 x 5 +… )

6. Solution of first and second order recurrence relations using

generating functions
First order recurrence relations

51. Obtain the generating function for the recurrence relation a n+1−an=3 n , n ≥ 0
with

a 0=1. Hence solve the relation.

52. Obtain the generating function for the recurrence relation a n+1−an=n 2 , n ≥ 0
with a 0=1. Hence solve the relation.

53. Obtain the generating function for the recurrence relation a n−3 an−1=n , n≥ 1
with

a 0=1. Hence solve the relation.

54. Obtain the generating function for the recurrence relation a n−4 an−1=0 ,n ≥ 1
with

a 0=1. Hence solve the relation.

55. Obtain the generating function for the recurrence relation a n−a n−1 =2 ,n ≥ 1
with a 0=6 . Hence solve the relation.

Second order recurrence relations

56. Obtain the generating function for the recurrence relation
a n+2−3 a n+1 +2 an =0 , n≥ 0 with a 0=1 and a 1=6. Hence solve the relation.

57. Obtain the generating function for the recurrence relation y n +2−4 y n+1 +3 y n=0 ,
with y 0=2 and y 1=4. Hence solve the relation.

58. Obtain a generating function for the recurrence relation

2
a r +5 ar −1+6 ar−2=3 r , r ≥2.
59. Obtain the generating function for the recurrence relation
a n+2−2 a n+1 +a n=2 ,n ≥ 0 with a 0=1 and a 1=2. Hence solve the relation.
n

60. Obtain the generating function for the recurrence relation

a n+2−5 a n+1 +6 a n=2 , n≥ 0 with a 0=3 and a 1=7. Hence solve the relation.