Quiz · Medium
Twenty counting questions: arrangements, committees, stars and bars, binomial coefficients, inclusion-exclusion, derangements and the pigeonhole principle.
The number of derangements of 4 objects, , is
6
9
12
24
D_4 = 4!(1 - 1 + 1/2 - 1/6 + 1/24) = 24 - 24 + 12 - 4 + 1 = 9.
How many ways can 5 different books be arranged on a shelf?
25
60
3125
120
Order matters and every book is used once: 5! = 120. 5^5 = 3125 would allow repeating books; 25 is 5^2.
How many distinct arrangements are there of the letters in STATISTICS?
10!/(3! 3! 2!)
10!
10!/(3! 3! 2! 2!)
10!/(3! 2!)
STATISTICS has 10 letters: S x3, T x3, I x2, A x1, C x1. Divide by 3!, 3! and 2! (A and C appear once, so they add nothing): 10!/(3! 3! 2!) = 50400. Dividing by an extra 2! undercounts.
A club has 7 members. In how many ways can a president, a vice president and a treasurer be chosen (different people)?
35
343
210
5040
Offices are distinct, so order matters: 7 * 6 * 5 = 210. 35 = C(7,3) ignores which office each person holds.
How many 5-card poker hands contain exactly four cards of the same rank (four of a kind)?
13 * C(4,4) * C(48,1) * 4
13 * 48 = 624
C(13,1) * C(52,4)
13 * 12 * 4
13 ranks, all 4 suits of that rank, and any of the 48 remaining cards. The other options overcount or count something unrelated.
In how many ways can a committee of 3 be formed from 5 men and 4 women if it must contain at least one woman?
74
84
80
64
Total C(9,3) = 84; all-men committees C(5,3) = 10; 84 - 10 = 74. Choosing one woman first and then any 2 others counts committees with several women more than once.
How many integer solutions does have with every ?
Stars and bars: 12 stars and 3 bars give C(15, 3) = 455. C(11, 3) counts positive solutions.
The coefficient of in is
252
45
10
210
C(10, 4) = 210. C(10, 5) = 252 is the middle coefficient; C(10, 2) = 45.
The coefficient of in is
10
40
20
80
The term is C(5,2)(2x)^2 y^3 = 10 * 4 = 40. Forgetting to square the 2 gives 10.
What is ?
64
128
256
512
Setting x = y = 1 in the binomial theorem gives 2^8 = 256.
Using Pascal's triangle shown, equals

5
10
15
20
Row 5 reads 1, 5, 10, 10, 5, 1; the entry for k = 3 is 10, the sum of 4 and 6 from row 4. Image: Conrad.Irwin / Drini, CC BY-SA 3.0, via Wikimedia Commons.
How many distinct shortest paths from A to B on the grid (right and up steps only)?
6
15
20
10
Each path has 3 R and 2 U steps: C(5, 2) = 10 arrangements.
Among 30 people, at least how many must share the same birth month (guaranteed)?
3
2
4
5
ceil(30/12) = 3, so some month has at least 3 people. Two would only be guaranteed with 13 people.
You take socks at random from a drawer with 8 red, 8 blue and 8 green socks. What is the smallest number that guarantees a matching pair?
4
3
5
9
Three colors are the boxes; 3 socks may all differ, but 4 socks force two of the same color.
How many numbers from 1 to 60 are divisible by 3 or 5?
20
32
28
12
Multiples of 3: 20; of 5: 12; of 15: 4. Inclusion-exclusion gives 20 + 12 - 4 = 28. Adding without subtracting the overlap gives 32.
True or false: the number of ways to seat n people around a circular table (rotations identical) is (n - 1)!.
True
False
Fix one person to break rotational symmetry, then arrange the other n - 1 in a line.
The Catalan number equals
46
52
252
42
252 / 6 = 42. The sequence runs 1, 1, 2, 5, 14, 42, so C_5 = 42.
How many bit strings of length 6 have an even number of ones?
16
24
36
32
Half of all 2^6 = 64 strings have an even number of ones (sum of even-indexed binomials = 2^5 = 32).
Which identity is the hockey-stick identity?
The hockey stick sums a diagonal of Pascal's triangle into the entry just below. The others are symmetry, Pascal's rule and a Vandermonde corollary.
Number of onto functions from a 4-element set to a 2-element set:
8
14
16
2
All functions: 2^4 = 16, minus the two constant functions: 14.