Combinations and Urn Models
A combination is an unordered selection of k objects from n, counted by the binomial coefficient C(n, k) = n!/(k!(n − k)!); urn models use combinations to count the ways of drawing balls with different colours. In brief: a team of 3 chosen from 10 people can be formed in C(10, 3) = 120 ways. If an urn holds 5 red and 3 blue balls and 3 balls are drawn without replacement, the probability of exactly 2 red is C(5, 2) · C(3, 1)/C(8, 3) = 10 · 3/56 ≈ 0.536.
When the order does not matter, each selection counts once, and the number of selections is smaller than the number of ordered ones by the factor k!. Combinations appear in the binomial theorem, in Pascal’s triangle and throughout probability. This guide derives the formula, shows its main properties, explains the urn model for the hypergeometric probability and combinations with repetition, with a table of binomial coefficients for n up to 10.
What is a combination?
A k-combination of an n-element set is a k-element subset. Each such subset can be arranged in k! orders, so the ordered selections V(n, k) = C(n, k) · k!. Therefore
C(n, k) = n!/(k!(n − k)!) = n(n − 1)⋯(n − k + 1)/k!, read “n choose k”. Other notations: nCk and the binomial coefficient written (n over k).
Example 1
C(5, 2) = 5 · 4/2 = 10. C(10, 3) = 10 · 9 · 8/6 = 120. C(52, 5) = 2,598,960 is the number of 5-card poker hands. C(49, 6) = 13,983,816 is the number of ways to choose 6 numbers from 49 in a lottery, so the chance of winning with one ticket is about 1 in 14 million.
What are the properties of C(n, k)?
- Symmetry: C(n, k) = C(n, n − k). Choosing the k objects to take is the same as choosing the n − k to leave. So C(10, 7) = C(10, 3) = 120.
- Edges: C(n, 0) = C(n, n) = 1, and C(n, 1) = n.
- Pascal’s rule: C(n, k) = C(n − 1, k − 1) + C(n − 1, k). Each entry of Pascal’s triangle is the sum of the two above it. Reason: for a special object, subsets that contain it number C(n − 1, k − 1), and those that do not number C(n − 1, k).
- Sum of a row: C(n, 0) + C(n, 1) + … + C(n, n) = 2n, the number of all subsets of an n-element set.
- Binomial theorem: (a + b)n = Σ C(n, k) an−kbk.
How do urn models work?
An urn contains balls of different colours. Drawing balls corresponds to selecting a subset, and the combinations count the possible draws. If every subset is equally likely, the probability of an event is (number of favourable subsets)/(total number of subsets).
Example 2: drawing without replacement
An urn has 5 red and 3 blue balls. Draw 3 balls at once. The total number of draws is C(8, 3) = 56. Exactly 2 red and 1 blue: C(5, 2) · C(3, 1) = 10 · 3 = 30, probability 30/56 ≈ 0.536. All red: C(5, 3) = 10, probability 10/56 ≈ 0.179. At least one blue is 1 − 10/56 = 46/56 ≈ 0.821. The number of red balls follows the hypergeometric distribution: P(X = r) = C(5, r)C(3, 3 − r)/C(8, 3) for r = 0, 1, 2, 3 with values 1/56, 15/56, 30/56, 10/56, which sum to 1.
Example 3: drawing with replacement
If each ball is returned before the next draw, the draws are independent. Then the probability of exactly 2 red in 3 draws is C(3, 2)(5/8)2(3/8) = 3 · (25/64)(3/8) = 225/512 ≈ 0.439.
Example 4: quality control
A box has 20 items, 4 defective. Inspect a sample of 5. The probability of no defective item is C(16, 5)/C(20, 5) = 4,368/15,504 ≈ 0.282. Exactly one defective: C(4, 1)C(16, 4)/C(20, 5) = 4 · 1,820/15,504 ≈ 0.470.
What are combinations with repetition?
When repetition is allowed and order does not matter (such as choosing 4 scoops of ice cream from 3 flavours), the number of selections is C(n + k − 1, k). The method: represent a selection by k stars separated by n − 1 bars, and count the arrangements of stars and bars. For n = 3 flavours and k = 4 scoops: C(6, 4) = 15.
Example 5
The number of non-negative integer solutions of x + y + z = 10 is C(12, 2) = 66. If each variable must be at least 1, substitute x′ = x − 1 etc., so x′ + y′ + z′ = 7 and C(9, 2) = 36 solutions.
Example 6: dominoes
A standard domino set has tiles with two ends marked 0 to 6: choosing 2 numbers from 7 with repetition: C(7 + 2 − 1, 2) = C(8, 2) = 28 tiles ✓.
More worked examples
Example 7: a committee with conditions
A committee of 4 is chosen from 6 men and 5 women, with at least 2 women. Cases: 2 women and 2 men: C(5, 2)C(6, 2) = 10 · 15 = 150. 3 women and 1 man: C(5, 3) · 6 = 60. 4 women: C(5, 4) = 5. Total: 215. Check by complement: C(11, 4) = 330, fewer than 2 women: 0 women C(6, 4) = 15, 1 woman 5 · C(6, 3) = 100, so 330 − 115 = 215 ✓.
Example 8: handshakes and diagonals
In a group of 12 people, each shakes hands once with everybody else: C(12, 2) = 66 handshakes. A polygon with n vertices has C(n, 2) − n diagonals.
Example 9: solving an equation
C(n, 2) = 45: n(n − 1)/2 = 45, so n2 − n − 90 = 0, and n = 10.
Example 10: a poker hand
The number of hands with exactly one pair: choose the rank of the pair (13), its 2 suits C(4, 2) = 6, the other 3 ranks from 12 (C(12, 3) = 220) and a suit for each (43 = 64): 13 · 6 · 220 · 64 = 1,098,240. The probability is 1,098,240/2,598,960 ≈ 0.4226.
Table of binomial coefficients
| n | k = 0 | k = 1 | k = 2 | k = 3 | k = 4 |
|---|---|---|---|---|---|
| 4 | 1 | 4 | 6 | 4 | 1 |
| 5 | 1 | 5 | 10 | 10 | 5 |
| 6 | 1 | 6 | 15 | 20 | 15 |
| 7 | 1 | 7 | 21 | 35 | 35 |
| 8 | 1 | 8 | 28 | 56 | 70 |
| 9 | 1 | 9 | 36 | 84 | 126 |
| 10 | 1 | 10 | 45 | 120 | 210 |
For larger k, use the symmetry C(n, k) = C(n, n − k). The values for k = 5 and larger: C(10, 5) = 252, C(9, 5) = 126, C(8, 5) = 56.
Where do combinations come from?
The binomial coefficients were known to Indian mathematicians such as Pingala (around the second century BCE) and Halayudha, to the Persian mathematician Al-Karaji and the Chinese Yang Hui before Pascal. Blaise Pascal’s 1654 treatise on the arithmetical triangle linked them to probability, and the notation C(n, k) and the term “combinations” became standard in the following centuries. The problem of the points that Pascal and Fermat solved by correspondence in 1654 is considered the beginning of probability theory.
Where are they used today?
Combinations are used in lotteries, in selecting samples in surveys and quality control, in genetics (the number of possible allele combinations), in network design (the number of possible connections C(n, 2) between n computers) and in the analysis of algorithms. The hypergeometric distribution of the urn model is used to test whether a sample deviates from a population.
Which mistakes are common?
Counting the order when it does not matter
For a committee, use C(n, k). Using V(n, k) overcounts by k!.
Adding instead of multiplying the choices from separate groups
For “2 men and 2 women”, multiply C(6, 2) · C(5, 2). Add only for different cases.
Forgetting the complement shortcut
“At least one” is easier as total − none.
Mixing up with and without replacement
Drawing balls at once or one after another without putting them back gives combinations (hypergeometric). With replacement, the draws are independent (binomial).