K.S.
INSTITUTE OF TECHNOLOGY, BENGALURU– 560109
DISCRETE MATHEMATICAL STRUCTURES
Question Bank
Module 4- The Principle of Inclusion and Exclusion
1. In how many ways can the 26 letters of the English alphabet be permuted so that none of
the patterns CAR, DOG, PUN or BYTE occurs?
2. In how many ways one can arrange the letters of the word CORRESPONDENTS so that
there are i) exactly 2 pairs of consecutive identical letters? ii) at least 3 pairs of
consecutive identical letters? iii) no pair of consecutive identical letters?
3. Identify the number of positive integers n such that 1 ≤ 𝑛 ≤ 100 and n is not divisible by
2, 3, or 5.
4. Identify the number of integers between 1 and 300 which are divisible by i) exactly two
of ii) at least two of iii) at least one of iv) none of .
5. Out of 30 students of a hostel 15 study history, 8 study economics, 6 study geography and
3 study all the three subjects. Show that 7 or more study none of the subjects.
6. There are 8 letters to 8 different people to be placed in 8 different addressed envelopes.
Find the number of ways of doing this so that at least one letter gets to the right person.
7. For the integers 𝑛, there are 11660 derangements where appear in first
five positions then identify the value of n.
8. Utilize the concept of derangements to Find the number of derangements of 1,2,3,4.
Mention them.
9. Define Derangement. In how many ways can each of 10 people select a left glove and a
right glove out of a total of 10 pairs of gloves so that no person selects a matching pair of
gloves?
10. Compute derangement of .
11. Make use of the expansion formula, obtain the rook polynomial for the board C.
12. Construct the rook polynomial for the board shown below:
1 2
3
4 5
6 7
13. Construct the rook polynomial for the chess board as shown in the figure.
14. Construct the rook polynomial for the board by using the expansion formula.
15. By using expansion formula, find the rook polynomial for the board C shown below:
1 2
3 4 5
16. Utilize the concept rook polynomials, Five teachers 𝑇1, 𝑇2, 𝑇3, 𝑇4, 𝑇5 are to be made
class teachers for five classes, 𝐶1, 𝐶2, 𝐶3, 𝐶4, 𝐶5, one teacher for each class. 𝑇1and 𝑇2 do
not wish to become the class teachers for 𝐶1or 𝐶2, 𝑇3 and 𝑇4 for 𝐶4 or 𝐶5 , and 𝑇5 for 𝐶3
or 𝐶4 or 𝐶5 . In how many ways can the teachers be assigned the work (without
displeasing any teacher)
17. Utilize the concept rook polynomials, An apple, a banana, a mango and an orange to be
distributed to 4 boys and . The boys and do not wish to have apple.
does not want banana or mango. refuses orange. In how many ways distribution can
be made so that all of them are happy.
18. Solve the recurrence relation: for 𝑛 given that .
19. Solve the recurrence relation 𝑛 = 𝑛 𝑛−1 where n ≥ 1and 0 = 1.
20. Utilize the concept of recurrence relation to find K, If is a solution of the recurrence
relation:
for 𝑛 and .
21. The number of virus affected files in a system is 1000(initially) and this increases 250%
every 2 hours. Make use of recurrence relation to determine the number of virus affected
files in the system after one day.
22. Solve the recurrence relation:
(i) 𝐶𝑛 = 3𝐶𝑛−1 − 2𝐶𝑛−2, 𝑓𝑜𝑟 𝑛 ≥2, given 𝐶1 = 5, 𝐶2 = 3.
(ii) 𝑛+2 − 3 𝑛+1 + 2 𝑛= 0, 0 = 1, 1 = 6.
(iii) for 𝑛 given .
(iv) 𝐹𝑛+2 = 𝐹𝑛+1 + 𝐹𝑛 where n ≥ 0 and 𝐹0 = 0, 𝐹1 =1.
(v) an-6an-1+9an-2=0, for 𝑛 given .
23. In how many ways 5 number of a’s, 4 number of b’s and 3 number of c’s can be arranged
so that all the identical letters are not in a single block?
24. solve the relation If and satisfy the recurrence
relation , for 𝑛 , find the constants b and cs.
******************************
Text Books:
1. Ralph P. Grimaldi, B V Ramana: “Discrete Mathematical Structures an Applied Introduction”, 5 th
Edition, Pearson Education, 2004.
2. Ralph P. Grimaldi: “Discrete and Combinatorial Mathematics”, 5th Edition, Pearson Education. 2004.
Reference Books:
1. Basavaraj S Anami and Venakanna S Madalli: “Discrete Mathematics – A Conceptbased approach”,
Universities Press, 2016
2. Kenneth H. Rosen: “Discrete Mathematics and its Applications”, 6th Edition, McGraw Hill, 2007.
3. Jayant Ganguly: “A Treatise on Discrete Mathematical Structures”, SanguinePearson, 2010.
4. D.S. Malik and M.K. Sen: “Discrete Mathematical Structures Theory and Applications, Latest Edition,
Thomson, 2004. 5. Thomas Koshy: “Discrete Mathematics with Applications”, Elsevier, 2005, Reprint
2008.
Web links:
[Link]
[Link]
[Link]
VTU e-Shikshana Program
VTU EDUSAT Program.