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.
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?
16
(ii) Determine the number of distinct terms in the expansion of ( 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 + x 2 + 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 + x 2 + 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 + x 2 + x 3 + x 4 + x 5 = 30, where

x 1 ≥ 2 , x 2 ≥ 3 , x 3 ≥ 4 , x 4 ≥ 2 , x 5 ≥ 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.
10
(ii) Determine the number of distinct terms in the expansion of ( w + x + y + z ) .

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 + x 2 + x 3 + x 4 = 7.
2. Binomial theorem and Multinomial theorem
Binomial theorem
11. Obtain the sums of all the coefficients in the expansions of
n
(b) ( x 1 + x 2 + … + x k )
n
(a) ( x + y )

Hence obtain the sum of all the coefficients in the expansions of each of the following
10 5 12
(i) ( x + y ) (ii) ( x + y + z + w ) (iii) ( x + 2 y - 3 z + 2 u + 3 v )
12
12. Determine the coefficient of x 9 y 3 in the expansion of ( 2 x - 3 y )

( )
15
0 2 2
13. Determine the coefficient of x in the expansion of 3 x -
x
10
14. Determine the coefficient of x 12 in the expansion of x 3 ( 1 - 2 x )

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
4
16. Determine the coefficient of xy z 2 in the expansion of ( 2 x - y - z ) .
7
17. Determine the coefficient of x 2 y 2 z 3 in the expansion of ( 3 x - 2 y - 4 z ) .
6
18. Determine the coefficient of x 11 y 4 in the expansion of ( 2 x 3 - 3 x y 2 + z 2 ) .
16
19. Determine the coefficient of a2 b 3 c 2 d 5 in the expansion of ( a + 2 b - 3 c + 2 d + 5 ) .
2 3 4 10
20. Determine the coefficient of x 1 x 3 x 4 x 5 in the expansion of ( x 1 + x 2 + x 3 + x 4 + x 5 ) .

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, Obtain the 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 B 1 , B 2 , B 3 , B 4 .
The boys B 1 and B 2 do not wish to have apple, the boy B 3 doesn’t want banana or mango and B 4
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 , C 3 , 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 P 1 , P 2 , P 3 , P 4 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. P 1 will not sit at T 1 or T 2, P 2 will not sit at T 2 , P 3 will
not sit at T 3 or T 4 and P 4 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.
3
41. (i) Find the sequence generated by the function ( 3 + x )

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

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

(ii) Find the generating function for the sequence: 02 , 12 , 22 , 32 , 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 , 4 3 , …

-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 , 4 3 , …

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

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

( 1 + x )4
46. Determine the coefficient of x 15 in
( 1 - x )4

x3 - 5 x
10
47. Determine the coefficient of x in 3
(1 - x )
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 + x 3 + x 4 + x 5 )( x 2 + x 3 + 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 + x 5 + 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
n
51. Obtain the generating function for the recurrence relation an + 1 - an = 3 , n ≥ 0 with

a0 = 1. Hence solve the relation.

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

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

a0 = 1. Hence solve the relation.

54. Obtain the generating function for the recurrence relation an - 4 an - 1 = 0 , n ≥ 1 with
a0 = 1. Hence solve the relation.

55. Obtain the generating function for the recurrence relation an - an - 1 = 2 , n ≥ 1 with a0 = 6 . Hence
solve the relation.
Second order recurrence relations

56. Obtain the generating function for the recurrence relation an + 2 - 3 an + 1 + 2 an = 0 , n ≥ 0 with a0 = 1
and a1 = 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.
2
58. Obtain a generating function for the recurrence relation ar + 5 ar - 1 + 6 ar - 2 = 3 r , r ≥ 2.
n
59. Obtain the generating function for the recurrence relation an + 2 - 2 an + 1 + an = 2 , n ≥ 0 with a0 = 1
and a1 = 2. Hence solve the relation.

60. Obtain the generating function for the recurrence relation an + 2 - 5 an + 1 + 6 an = 2 , n ≥ 0 with a0 = 3
and a1 = 7 . Hence solve the relation.