This set covers combinatorics, the counting part of Discrete Mathematics. It includes permutations with repeated letters, circular arrangements, committee selection, stars and bars, the pigeonhole principle, inclusion-exclusion, derangements, Catalan numbers and the binomial theorem. Many questions are short numerical problems of the kind set in GATE CS, university exams and the quantitative aptitude rounds of campus placements, and each explanation shows how to get the count quickly.
How to practise: read each question and tap the option you think is correct. You will see right away whether you got it, along with a short explanation, and your score is tracked at the bottom of the screen. This set has 18 questions.
Topics covered in this set
- Permutations with repetition and circular arrangements
- Combinations and committee selection
- Stars and bars (integer solutions)
- Pigeonhole principle
- Inclusion-exclusion and derangements
- Binomial theorem and identities
- Catalan numbers and lattice paths
Discrete Mathematics MCQs with answers and explanations
Q1. How many distinct arrangements can be made of the letters of the word BANANA?
a) 120
b) 720
c) 60
d) 180
Q2. A committee of 3 men and 2 women is to be chosen from 6 men and 5 women. In how many ways can this be done?
a) 462
b) 330
c) 150
d) 200
Q3. What is the minimum number of people needed to guarantee that at least 3 of them were born in the same calendar month?
a) 24
b) 25
c) 36
d) 37
Q4. How many integers from 1 to 100 are divisible by none of 2, 3 and 5?
a) 74
b) 22
c) 26
d) 30
Q5. Five letters are placed in five addressed envelopes. In how many ways can every letter go into a wrong envelope?
a) 120
b) 53
c) 40
d) 44
Q6. What is the coefficient of x^3 in the expansion of (2x + 1)^5?
a) 80
b) 10
c) 40
d) 160
Q7. How many integer solutions does x1 + x2 + x3 + x4 = 12 have with every xi ≥ 2?
a) 455
b) 165
c) 35
d) 56
Q8. Six people sit around a round table. In how many arrangements do two particular people sit next to each other?
a) 24
b) 120
c) 240
d) 48
Q9. How many bit strings of length 8 contain at least two 1s?
a) 247
b) 248
c) 255
d) 219
Q10. How many onto functions are there from a set of 5 elements to a set of 3 elements?
a) 243
b) 150
c) 60
d) 125
Q11. What is the minimum number of integers that must be chosen from {1, 2, ..., 20} to guarantee that two of the chosen integers sum to 21?
a) 10
b) 12
c) 21
d) 11
Q12. How many diagonals does a convex polygon with 10 sides have?
a) 35
b) 45
c) 90
d) 70
Q13. In how many ways can 5 boys and 3 girls stand in a row so that no two girls are adjacent?
a) 40320
b) 14400
c) 2880
d) 720
Q14. How many shortest lattice paths go from (0, 0) to (4, 3) using unit steps right and up?
a) 12
b) 70
c) 35
d) 128
Q15. What is the term independent of x in the expansion of (x + 1/x^2)^9?
a) 84
b) 36
c) 126
d) 9
Q16. How many valid (balanced) strings can be formed with 4 pairs of parentheses?
a) 8
b) 14
c) 16
d) 70
Q17. How many 4-digit numbers (1000 to 9999) have all distinct digits?
a) 4536
b) 5040
c) 3024
d) 9000
Q18. What is the value of C(10,0) - C(10,1) + C(10,2) - ... + C(10,10)?
a) 1
b) 0
c) 1024
d) 512
Quick revision notes
- Arrangements of n objects with repeats n1, n2, ...: n!/(n1! n2! ...).
- Circular arrangements of n distinct objects: (n - 1)!.
- Non-negative integer solutions of x1 + ... + xk = n: C(n + k - 1, k - 1).
- Pigeonhole: n items in k boxes force some box to hold at least ceil(n/k) items.
- Derangements: D(n) = n! Σ (-1)^k / k!; D(4) = 9, D(5) = 44.
- General term of (a + b)^n: C(n, k) a^(n-k) b^k; Σ C(n, k) = 2^n.
- Catalan number C_n = C(2n, n)/(n + 1): 1, 1, 2, 5, 14, 42, ...
- Onto maps from an m-set to an n-set: Σ (-1)^k C(n,k)(n-k)^m.
Frequently asked questions
When should I use permutations and when combinations?
Use permutations when the order or the position of the chosen objects matters, such as seating or arranging letters. Use combinations when only the chosen group matters, such as a committee or a hand of cards.
How do I apply the pigeonhole principle to 'guarantee' questions?
Imagine the worst case, where items are spread as evenly as possible across the boxes without meeting the condition, and then add one. For example, 2 people per month across 12 months is 24, so the 25th person forces three to share a month.
What is a derangement?
A derangement is a permutation in which no element stays in its original position. Inclusion-exclusion gives the count, and D(n) is close to n!/e for large n.
Comments
Post a Comment