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
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.
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
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
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
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
Explanation: 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
View Answer
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
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
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
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.
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
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.
- Practice BCA MCQs
- Check BCA Books
- Apply for Computer Science Internship
- Practice Computer Science MCQs
- Check Discrete Mathematics Books
