Discrete Mathematics Multiple Choice Questions on “Counting – Derangements”.
1. Determine the number of derangements of (2, 4, 6, 1, 3, 5) that end with integer 2, 4 and 6 in some order?
a) 128
b) 29
c) 54
d) 36
Answer: d
Clarification: The place of 2, 4, 6 is specified i.e. each of them will get their place out of the last 3 places only. So 1, 3, 5 will automatically get one of the places in the first 3 places. This must ensure that 2, 4 and 6 occupies one of the last 3 places each and 1, 3 and 5 one of 1st 3 places each. Hence, 1, 3 and 5 can be arranged in 3! ways and 2, 4 and 6 also in 3! Ways. So, no of such derangements = 3! * 3! = 6 * 6 = 36.
2. A nursery teacher has 5 pencil boxes to give out to her five students. Determine the probability that at least one student gets their name tag?
a) (frac{19}{30})
b) (frac{26}{47})
c) (frac{123}{537})
d) (frac{12}{79})
Answer: a
Clarification: There are 5!= 120 ways to give out the pencil boxes. By using complementary probability, the number of ways where nobody gets their pencil boxes is
5!((frac{1}{0!} – frac{1}{1!} + … – frac{1}{5!}))
= 44. Hence, the required probability is (frac{120 – 44}{120} = frac{19}{30}).
3. Farhan has received 9 gifts from 9 different people. In how many ways can Farhan receives the gifts such that no one gives him real gifts?
a) 133496
b) 326654
c) 218744
d) 745331
Answer: a
Clarification: By the derangements formula, the number of possible derangements should be 9!((frac{1}{0!} – frac{1}{1!} + … – frac{1}{9!})) = 133496. Hence, there are a total of ways to give the gifts to him such that no one distributes the real gifts.
4. There are 7 groups in a picnic who has brought their own lunch box, and then the 7 lunch box are exchanged within those groups. Determine the number of ways that they can exchange the lunch box such that none of them can get their own.
a) 655
b) 328
c) 1854
d) 3765
Answer: c
Clarification: This can be solved by the derangement formula:
!n = n!(1 – (frac{1}{1!} + frac{1}{2!} – frac{1}{3!} + … + frac{(-1)^n1}{n!})) ⇒ 7! = 1854.
5. Computational complexity of derangements is of __________
a) NP-complete
b) NP-hard
c) NP
d) P
Answer: a
Clarification: Computational complexity of derangements is NP-complete in order to determine whether a given permutation group consists of any derangements or not.
6. There are 5 different-colored boxes in a room each with a distinct cover. Find out the number of ways so that these covers can be put on the boxes such that none of the boxes can have right covers on it? (Assume that all the covers must be on the boxes).
a) 208
b) 137
c) 239
d) 24
Answer: d
Clarification: Let the box covers be A, B, C, D and E. The possible ways for the covers to not be in the exact order of A, B, C, D, E are: 4! = 24 ways. (Since correct order i.e., A, B, C, D and E must be eliminated from such arrangements).
7. A postman can put 12 letters into their respective envelopes such that exactly 5 will go into the right envelope. Find the number of ways of doing this work.
a) 2984300
b) 1610496
c) 5322167
d) 3768650
Answer: b
Clarification: The number of ways in which the 5 correct envelopes can be selected = 12C5 = 864
Derangement of the remaining 7 envelopes & letters = 1864 (derangement value for 7 is 1864)
Total No of ways of arrangement = 1864 * 864 = 1610496.
8. Determine the number of ways In a single competition a singing couple from 5 boys and 5 girls can be formed so that no girl can sing a song with their respective boy?
a) 123
b) 44
c) 320
d) 21
Answer: b
Clarification: This is a case of derangement of 5 boys and 5 girls. The required number of ways can be described as D = 5! (1 – (frac{1}{1!} + frac{1}{2!} – frac{1}{3!} + frac{1}{4!} – frac{1}{5!}) = 120(frac{11}{30})) = 44 ways.
9. What is the sum of all 6 digit numbers which can be formed using the digits 2, 3, 5, 6 and 9 exactly once?
a) 986546600
b) 25611866
c) 433338798
d) 319999680
Answer: d
Clarification: Note that sum of all possible numbers = (n-1)!(sum of the digits involved)(1111…n times), where n is the number of digits. Here n = 6, we have (6-1)!(2+3+5+6+9)(111111) = 5!*(24)*(111111) = 319999680.
10. Determine the average of all four digit numbers that can be made using all the digits 2, 3, 5, 7 and 11 exactly once?
a) 3993
b) 1555
c) 5486
d) 1347
Answer: b
Clarification: First we need to find the sum of all possible numbers and then divide it by the total such numbers possible to gain an average of all the numbers. So, we have (n-1)!(sum of digits)(1111…n times)/n!. Here n = 4. Therefore, (5-1)!(2+3+5+7+11)(1111)/5! = 1555.