Discrete Mathematical Structures (BCS405A)

Module 2: Fundamental Principle of Counting

1.a)State sum and product rule of counting. Give one example for each.
b) Suppose a library has 12 books on mathematics, 10 books on physics, 16 books on chemistry and 11 books on
computer science. In how many ways a student can choose (i) one of these books for study (ii) two of these books
for study (iii) one physics and one chemistry books (iv) two chemistry and one computer science books (v) one from
each subject.
c) Determine the number of 6-digit integers in which (i) no digit is repeated (ii) no digit is repeated and it is even
(iii) no digit is repeated and it is divisible by 5.
d) In a certain implementation of the programming language Pascal an identifier consists of a single letter or a letter
followed by up to seven symbols, which may be letters or digits(26 letters, 10 digits). There are 36 reserved words.
How many distinct identifiers are possible in this version of Pascal?

2. a) 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 (i) the books in each particular
subject must all be together? (ii) only the mathematics must be together
b) How many arrangements are there for all letters in the word SOCIOLOGICAL? In how many of these
arrangements (i) A & G are adjacent? (ii) all vowels are adjacent?
c) How many positive integers n can we form using the digits 3,4,4,5,5,6,7 if we want n to exceed 50, 00, 000?
d) How many numbers greater than 1000000 can be formed using the digits 1, 2, 2, 2, 4, 4, 0?

3. a) Find the number of committees of 5 that can be selected from 7 men and 5 women if the committee is to
consist of at least 1 man and at least one woman.
b) A certain question paper contains 3 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?
c) 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.
d) Find the number of arrangements of all the letters in TALLAHASSEE. How many of these arrangements have no
adjacent A’s ?

4.a) Find the coefficients of (i) x9 y 3 in the expansion of  2 x  3 y 

12

(ii) x12 in the expansion of x 3 1  2 x 

10

b) Determine the coefficients of (i) xyz 2 in the expansion of  2x  y  z 

4

(ii) x 2 y 2 z 3 in the expansion of  3 x  2 y  4 z   

6
(iii) x11 y 4 z 2 in the expansion of 2 x3  3xy 2  z 2
7

(iv) a 2b3c 2 d 5 in the expansion of  a  2b  3c  2d  5 

16

5.a) A cake shop sells 20 kinds of cakes. If there are at least a dozen cakes of each kind, in how many ways a dozen
cakes can be chosen?
b) 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?
c) A message is made up of 12 different symbols and is to be transmitted through a communication channel. In
addition to the 12 symbols, the transmitter will also send a total of 45 blank spaces between the symbols, with at
least three spaces between each pair of consecutive symbols. In how many ways can the transmitter send such a
message?
6. Mathematical Induction Principle

Module 4: Principle of Inclusion and exclusion

1. Out of 30 students in a hostel 15 study history, 8 study economics, and 6 study geography. It is known that 3
students study all these subjects. Show that 7 or more students study none of these subjects.
2. Determine the number of positive integers n such that 1  n  100 and n is not divisible by 2, 3 or 5.
3. Find the number of permutations of the digits 1 through 9 in which the blocks 36, 78, 672 do not appear.
4. Find the number of permutations of the English letters which contain (i) at least one (ii) none (iii) exactly two
(iv) exactly three (v) at least three, of the patterns CAR, DOG, PUN and BYTE.
5. In how many ways can one arrange the letters in the word CORRESPONDENTS so that (i) there is no pair of
consecutive identical letters? (ii) There are exactly two pairs of consecutive identical letters? (iii) There are at
least three pairs of consecutive identical letters?
6. In how many ways can one arrange the letters in the word ARRANGEMENT so that (i) there is no pair of
consecutive identical letters? (ii) There are exactly two pairs of consecutive identical letters? (iii) There are at
least three pairs of consecutive identical letters?

Derangements

1. Define derangements. Find the number of derangements of 1, 2, 3, 4. List them.

2. Find the number of derangements of integers from 1 to n (inclusive) such that, in each derangement (i) the
elements I the first k places are 1, 2, 3, . . ., k in some order. (ii) the elements in first n-k places are k+1, k+2, .
. ., n in some order (0 < k < n).
3. There are eight letters to eight different people to be placed in eight different addressed envelopes. Find the
number of ways of doing so that at least one letter gets to the right person.
4. Each of the n students is given a book. The books are to be returned and redistribute to the same students. In
how many ways can the two distributions be made so that no student will get the same in both the
distributions.

Rook polynomials

1. Find the rook polynomial for the unshaded region

 2. Arrangements with forbidden positions
a. An apple, a banana, a mango and an orange are to be distributed to four boys B1, B2, B3, and B4. 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 the distribution can be made so that no boy is displeased?
b. Four persons P1, P2, P3, P4 who arrive late for a dinner party find that only one chair at each of five
tables T1, T2, T3, T4, T5 is vacant. P1 will not sit at T1or T2, P2 will not sit at T2, P3 will not sit at T3 or
T4, P4 will not sit at T4 or T5. Find the number of ways they can occupy the vacant chairs.
c. Five teachers T1, T2, T3, T4, and T5 are to be made class teachers for five classes C1, C2,C3,C4,and C5,
one teacher for each class. T1 and T2 do not wish to become the class teachers for C1 or C2, T3 and T4
for C4 or C5, T5 for C3 or C4 or C5. In how many ways can the teachers be assigned the work (without
displeasing any teacher)?

Recurrence relations
I. Solve the following recurrence relations:
1. an  an1  6an2  0, n  2. Given a0  1 and a1  8 .
2. an  6an1  9an2  0, n  2. Given a0  5 and a1  12 .
3. Dn  bDn1  b2 Dn2  0, n  3. Given D1  b  0 and D2  0 .
4. an  7an1 , n  1. Given a2  98
5. an  an1  2n  1, n  2. Given a1  4 .
II.
6. an1  kan , n  0 with Given a3  153 and a5  1377 . What is k ?
49 2401
7. The number of virus affected files in a system is 1000 (to start with) and this increases 250% every 2
hours. Use a recurrence relation to determine the number of virus affected files in the system after one
day.