12. Counting
nCk, restrictions first, glue trick for adjacent items, 2^n subsets.
Core ideas
- Order does not matter: nCk = n! / (k!(n-k)!). Order matters: multiply slots.
- Handle restrictions FIRST: place the constrained people or seats, then fill the rest freely.
- Glue trick: items that must sit together become one block; arrange the blocks, then multiply by arrangements inside the block.
- "Must not both" or "at least" often falls fastest to total minus the bad cases. A set of n items has 2^n subsets.
Worked example 1
A club of 8 people must choose a 3-person committee, but Ann and Bob refuse to serve together. How many committees are possible?
Show solution
Total committees with no restriction: 8C3 = (8 * 7 * 6)/(3 * 2 * 1) = 56. Bad committees contain both Ann and Bob plus one of the other 6 people: 6 of them. Subtract: 56 - 6 = 50. Total minus bad beats casework here.
Worked example 2
Five different books are arranged on a shelf. In how many arrangements are the two math books next to each other?
Show solution
Glue the two math books into one block, giving 4 objects to arrange: 4! = 24 ways. Inside the block the two math books can sit in 2! = 2 orders. Multiply: 24 * 2 = 48 arrangements.
Practice set
Question 1
In how many different orders can 4 distinct books be arranged in a row on a shelf?
Fill the positions one at a time and multiply the number of options.
There are 4 choices for the first position, 3 for the second, 2 for the third, and 1 for the last: 4! = 4 * 3 * 2 * 1 = 24.
Question 2
A committee of 4 people is to be chosen from 6 men and 4 women. If the committee must include exactly 2 women, how many different committees are possible?
Handle the restriction first: pick the women, then pick the men, and multiply.
Choose 2 of the 4 women: 4 choose 2 = 6 ways. Choose 2 of the 6 men: 6 choose 2 = 15 ways. Multiply: 6 * 15 = 90. Choice E, 210, is 10 choose 4, which ignores the restriction.
Question 3
Five people, including Ana and Ben, are to stand in a row for a photo. If Ana and Ben must stand next to each other, how many different arrangements are possible?
Glue the required pair into one unit, arrange the units, then unglue.
Treat Ana and Ben as a single glued unit, giving 4 units to arrange: 4! = 24 ways. Ana and Ben can swap within the unit: times 2. Total 24 * 2 = 48. Choice A forgets the internal swap; choice E, 120, ignores the restriction entirely.
Question 4
A 5-digit code uses each of the digits 1, 2, 3, 4, and 5 exactly once. In how many such codes does the digit 1 appear somewhere to the left of the digit 2 ?
By symmetry, compare codes where 1 is left of 2 with codes where 2 is left of 1.
There are 5! = 120 codes in total. In every code, either 1 is left of 2 or 2 is left of 1, and by symmetry these two cases are equally common. So exactly half the codes qualify: 120/2 = 60. Choice A, 24, comes from forcing 1 and 2 to be adjacent.