Discrete Mathematics Questions and Answers – Counting – Derangements

«
»

This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses 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
View Answer

Answer: d
Explanation: 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.
advertisement

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}\)
View Answer

Answer: a
Explanation: 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
View Answer

Answer: a
Explanation: 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
View Answer

Answer: c
Explanation: 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
View Answer

Answer: a
Explanation: Computational complexity of derangements is NP-complete in order to determine whether a given permutation group consists of any derangements or not.
advertisement

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
View Answer

Answer: d
Explanation: 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
View Answer

Answer: b
Explanation: 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
View Answer

Answer: b
Explanation: 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
View Answer

Answer: d
Explanation: 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.
advertisement

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
View Answer

Answer: b
Explanation: 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.

Sanfoundry Global Education & Learning Series – Discrete Mathematics.

To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn