Difficulty: Intermediate | Prerequisites: Part 1 counting principles (product rule, division rule), factorial notation
Tags: binomial coefficient, permutations, combinations, Pascal's triangle, Catalan numbers, stars and bars, distributions, discrete mathematics, CS foundations, Purdue
Once you have the four basic counting rules (product, sum, inclusion-exclusion, division), the next layer is learning how to count selections and arrangements from a set. This is where permutations and combinations live. Binomial coefficients, which count combinations, turn up everywhere: probability distributions, algorithm analysis, the binomial theorem in algebra, and even data compression. This material also introduces two more advanced tools, the stars-and-bars technique for distribution problems and Catalan numbers, which count a surprising variety of structures in computer science.
Permutations count ordered arrangements; combinations count unordered selections. Binomial coefficients are the formula behind combinations, and Pascal's triangle gives a quick way to compute them. Distribution problems (identical objects into distinct bins) use the stars-and-bars formula. Catalan numbers count balanced parenthesisations, binary trees, and several other recursive structures.
Permutation
An ordered arrangement of objects. The number of ways to arrange r objects chosen from n distinct objects is P(n, r) = n! / (n − r)!. Think of it as: you care about who finishes first, second, third, not just who placed.
Combination
An unordered selection of objects. The number of ways to choose r objects from n distinct objects is C(n, r) = n! / [r!(n − r)!]. In simple terms, this means you only care about which objects are in the group, not what order they appear in.
Binomial coefficient
Another name for C(n, r), written as "n choose r". It counts unordered selections and also gives the coefficients in the expansion of (a + b)ⁿ. The two meanings (counting selections, algebraic expansion) are the same number, which is why the name sticks.
Pascal's triangle
A triangular array where each entry is the sum of the two entries directly above it. Row n of Pascal's triangle contains the binomial coefficients C(n, 0), C(n, 1), …, C(n, n). It provides a quick lookup and reveals symmetry properties.
Catalan number
The nth Catalan number is Cₙ = (1 / (n + 1)) × C(2n, n). It counts a family of combinatorial structures including valid sequences of n pairs of parentheses, the number of distinct binary trees with n internal nodes, and the number of ways to triangulate a polygon with n + 2 sides. Think of it as the "go-to" sequence whenever a problem involves nested or recursive pairing.
Stars and bars (balls into bins)
A counting technique for distributing n indistinguishable objects into k distinguishable bins. The count is C(n + k − 1, k − 1). The name comes from visualising the objects as stars and the dividers between bins as bars.
A permutation is a selection where the sequence of chosen items is significant.
Formula: P(n, r) = n! / (n − r)!
This is just the product rule applied step by step: n choices for the first slot, (n − 1) for the second, down to (n − r + 1) for the rth slot.
Example – prizes: Awarding first, second, and third prizes among 100 contestants. P(100, 3) = 100 × 99 × 98 = 970,200.
When r = n, you are arranging all n objects, and P(n, n) = n!.
A combination is a selection where only the membership of the group matters, not its internal order.
Formula: C(n, r) = n! / [r!(n − r)!]
You can derive this from permutations: C(n, r) = P(n, r) / r!, because each unordered group of r items corresponds to r! different ordered arrangements.
Example – poker: The number of 5-card hands from a standard 52-card deck is C(52, 5) = 2,598,960.
Symmetry property: C(n, r) = C(n, n − r). Choosing which r items to include is the same as choosing which (n − r) items to exclude.
The binomial theorem states: (a + b)ⁿ = Σ (from r = 0 to n) C(n, r) × aⁿ⁻ʳ × bʳ
Each term in the expansion has a binomial coefficient as its multiplier.
Example – expansion term: To find the coefficient of x¹²y¹³ in (2x − 3y)²⁵:
The relevant term uses r = 13 (the exponent on y), so the coefficient is C(25, 13) × 2¹² × (−3)¹³.
Note the sign: (−3)¹³ is negative, so the overall term carries a minus sign.
Pascal's identity: C(n, r) = C(n − 1, r − 1) + C(n − 1, r)
This says: to choose r items from n, either the nth item is in your selection (and you choose r − 1 more from the remaining n − 1) or it is not (and you choose all r from the remaining n − 1).
Pascal's triangle is built row by row using this identity, starting from C(0, 0) = 1.
Useful properties visible in the triangle:
Symmetry: each row reads the same forwards and backwards.
Row sums: the entries in row n sum to 2ⁿ (this corresponds to the total number of subsets of an n-element set).
Problem type: distributing n identical objects into k distinct bins.
Formula: C(n + k − 1, k − 1)
Visualise n stars (the objects) in a line, with (k − 1) bars inserted among them to create k groups.
The total number of symbols is n + k − 1, and you are choosing where to place the k − 1 bars.
Example: Distributing 10 identical balls into 4 distinct boxes: C(10 + 4 − 1, 4 − 1) = C(13, 3) = 286 ways.
This assumes each bin can hold zero or more objects. If each bin must have at least one, place one object in each bin first, then distribute the remaining (n − k) objects: C(n − 1, k − 1).
The nth Catalan number: Cₙ = (1 / (n + 1)) × C(2n, n)
First several values: C₀ = 1, C₁ = 1, C₂ = 2, C₃ = 5, C₄ = 14, C₅ = 42.
Catalan numbers count:
The number of valid arrangements of n pairs of parentheses.
The number of distinct full binary trees with n + 1 leaves.
The number of ways to parenthesise a product of (n + 1) numbers.
The number of monotonic lattice paths from (0, 0) to (n, n) that do not cross the diagonal.
These appear in compiler design (expression parsing), data structure enumeration, and computational geometry.
Concept | Formula |
|---|---|
Permutations | P(n, r) = n! / (n − r)! |
Combinations | C(n, r) = n! / [r!(n − r)!] |
Pascal's identity | C(n, r) = C(n − 1, r − 1) + C(n − 1, r) |
Binomial theorem | (a + b)ⁿ = Σ C(n, r) aⁿ⁻ʳ bʳ |
Stars and bars | C(n + k − 1, k − 1) |
Catalan number | Cₙ = (1 / (n + 1)) × C(2n, n) |
Combinations are the basis of lottery probability calculations and are used in machine learning to count possible feature subsets. The binomial theorem powers the binomial probability distribution, which models coin flips, quality control sampling, and A/B testing. Stars and bars appears in resource allocation problems, for example distributing identical tasks across servers. Catalan numbers crop up in compiler design when counting the number of distinct parse trees for an expression, and in network routing when counting valid paths.
The most common mistake is using permutations when combinations are needed, or vice versa. Ask: "Does the order of my selection matter?" If you are forming a committee, order does not matter (combination). If you are assigning ranked prizes, order matters (permutation).
Students often forget that C(n, r) = C(n, n − r). Exam questions sometimes present the version with the larger r to see if you simplify before computing.
With the binomial theorem, students frequently drop the sign when b is negative. Track the sign of each factor separately; (−3)¹³ is negative, but (−3)¹² is positive.
In stars-and-bars problems, students sometimes confuse which number goes where in C(n + k − 1, k − 1). Remember: n is the number of objects, k is the number of bins, and you are choosing positions for the (k − 1) dividers.
⚠️ "Permutation or combination?" is almost guaranteed to appear, often disguised. Look for language like "arrange" or "order" (permutation) versus "choose," "select," or "group" (combination).
⚠️ Binomial theorem questions frequently ask for a specific term's coefficient. Make sure you match the exponents to the correct r value and handle signs carefully.
⚠️ Pascal's identity is a common proof question. Be ready to give both the algebraic proof (expand the factorials) and the combinatorial proof (the "in or out" argument).
⚠️ Stars-and-bars problems may add constraints like "each bin gets at least one." Remember the adjustment: distribute (n − k) objects after placing one in each bin.
⚠️ Catalan numbers are less frequently examined in detail, but knowing the first few values and the parenthesisation interpretation is useful for quick-answer questions.
True or false: P(n, r) is always greater than or equal to C(n, r) for valid n and r.
Fill in the blank: C(n, r) = C(n, ______).
True or false: The sum of all entries in row 6 of Pascal's triangle is 64.
Fill in the blank: The number of ways to distribute 8 identical coins into 3 distinct jars is C(______, ______).
True or false: The 4th Catalan number (C₄) is 14.
Answers: 1. True (C(n, r) = P(n, r) / r!, and r! ≥ 1). 2. n − r. 3. True (2⁶ = 64). 4. C(10, 2), because n + k − 1 = 10, k − 1 = 2. 5. True.
Q: A club of 20 members needs to choose a president, vice-president, and secretary. How many ways can this be done?
A: Order matters (distinct roles), so this is a permutation. P(20, 3) = 20 × 19 × 18 = 6,840.
Q: From the same club of 20, how many ways can a 3-person committee be chosen (no assigned roles)?
A: Order does not matter, so this is a combination. C(20, 3) = 20! / (3! × 17!) = 1,140.
Q: What is the coefficient of x⁴y⁶ in the expansion of (x + y)¹⁰?
A: The term with x⁴y⁶ has r = 6 (or equivalently 10 − r = 4). The coefficient is C(10, 6) = C(10, 4) = 210.
Q: How many ways can you distribute 7 identical apples into 3 distinct baskets, if each basket must have at least one apple?
A: Place one apple in each basket first (using 3 apples), then distribute the remaining 4 into 3 baskets with no restriction. C(4 + 3 − 1, 3 − 1) = C(6, 2) = 15.
Q: How many valid sequences of 3 pairs of parentheses are there?
A: This is the 3rd Catalan number. C₃ = (1 / 4) × C(6, 3) = (1 / 4) × 20 = 5. The sequences are: ((())), (()()), (())(), ()(()), ()()().
Permutations and combinations build directly on the product rule and division rule from Part 1 of these notes. Binomial coefficients feed into probability theory, where C(n, r) appears in the binomial distribution formula. Catalan numbers connect to recursion and dynamic programming in algorithm design, since many Catalan-counted structures have natural recursive definitions. The stars-and-bars technique reappears in generating functions, an advanced combinatorics tool used to solve recurrence relations.
permutations, combinations, n choose r, binomial coefficient, binomial theorem, Pascal's triangle, Pascal's identity, nCr, nPr, ordered selection, unordered selection, stars and bars, balls into bins, distributions, Catalan numbers, parenthesisation, binary tree counting, discrete maths, CS 182, foundations of computer science, combinatorics