Difficulty: Intermediate | Prerequisites: Basic set theory, factorial notation, familiarity with the binomial coefficient C(n, k).
Combinatorics is the branch of mathematics concerned with counting arrangements, selections, and distributions of objects. It underpins probability, algorithm analysis, and nearly every discrete maths exam you will sit. If you can count the number of ways something can happen, you can find its probability, its complexity, or its expected value. You should already be comfortable with factorials and the idea that order sometimes matters and sometimes does not.
TL;DR: Counting problems reduce to a small toolkit: the sum rule (choose from disjoint options), the product rule (choose in sequence), combinations (choose a subset), the multinomial coefficient (arrange items with repeats), and stars and bars (distribute identical items). Knowing which tool fits which problem is 90% of the work.
Sum rule (rule of sum)
If a task can be done in one of several mutually exclusive ways, the total count is the sum of the counts for each way. In simple terms, if you are picking from Group A or Group B with no overlap, you add the sizes.
Product rule (rule of product)
If a task consists of a sequence of independent choices, the total count is the product of the number of options at each step. Think of it as multiplying together the number of choices you make in sequence.
Combination, C(n, k)
The number of ways to choose k items from n distinct items when order does not matter: C(n, k) = n! / (k!(n - k)!). In simple terms, this is "how many groups of k can I pull from n?"
Multinomial coefficient
A generalisation of the binomial coefficient. The number of ways to arrange n objects where there are groups of identical items of sizes n₁, n₂, ..., nₖ: n! / (n₁! · n₂! · ... · nₖ!). Think of it as the number of distinct orderings when some items are indistinguishable from one another.
Stars and bars (combinations with repetition)
A method for counting how many ways to distribute n identical items into k distinct bins. The formula is C(n + k - 1, k - 1). In simple terms, imagine n stars in a row and k - 1 dividers: every arrangement of stars and dividers gives a different distribution.
Partition of a set
A way of splitting all elements of a set into non-overlapping, exhaustive groups (piles). When the piles are unordered (unlabelled), you divide by the number of ways to rearrange identical-sized piles.
Inclusion-exclusion (for counting selections across categories)
When selecting items that must span multiple categories, you sum over all valid distributions of items across those categories. Each valid split contributes a product of combinations, one per category.
When you have several disjoint sets of objects, the sum rule tells you how many ways to pick one object from any set. If there are 8 English books, 7 French books, and 5 German books (all different), the number of ways to select 1 book is:
8 + 7 + 5 = 20
The product rule kicks in when you make multiple sequential choices. Selecting one book from each language gives 8 × 7 × 5 ways.
Use C(n, k) when you need to choose k items from n and the order of selection does not matter.
Choosing a 5-player basketball team from 10 players (no positions): C(10, 5)
If 2 specific players must be on the team, they are locked in, and you choose the remaining 3 from the other 8: C(8, 3)
The key question is always: does order matter? If you are just forming a group (no roles, no ranking), it does not, and you use combinations.
When you must choose k items from several groups and every group must be represented, you cannot use a single combination. Instead, enumerate the valid ways to split k across the groups, and for each split take the product of individual combinations.
Example: Select 4 books covering all three languages (English, French, German) from 8E, 7F, 5G. Each language must contribute at least 1 book. The valid splits of 4 books across 3 languages (each ≥ 1) are:
(2, 1, 1): C(8,2) · C(7,1) · C(5,1)
(1, 2, 1): C(8,1) · C(7,2) · C(5,1)
(1, 1, 2): C(8,1) · C(7,1) · C(5,2)
Total = sum of all three products.
The technique is: list the integer partitions of k into the required number of groups (each ≥ 1), then for each partition compute the product of the per-group combinations and sum.
When you arrange n objects where some are identical, the total number of distinct arrangements is n! divided by the factorial of each group of identical items.
Rolling a 20-sided die 6 times and getting exactly one 11, three 5s, and two 16s: the 6 rolls have specific values, and we need the number of ways to arrange these outcomes across the 6 positions. That is the multinomial coefficient 6! / (1! · 3! · 2!) = 60.
The multinomial coefficient also applies to forming numbers from digits with repeats.
Example: The digits 1, 2, 2, 4, 6, 6, 6 (seven digits total) can be arranged in 7! / (1! · 2! · 1! · 3!) distinct ways in total. When a constraint fixes the leading digit, you fix that digit and count the arrangements of the remaining six digits, adjusting the factorial counts accordingly.
Leading digit is 6: remaining digits are 1, 2, 2, 4, 6, 6. All arrangements of these 6 digits give numbers starting with 6,000,000+, which are all above 4,500,000. Count: 6! / (1! · 2! · 1! · 2!)
Leading digit is 4: remaining digits are 1, 2, 2, 6, 6, 6. All arrangements start with 4,000,000. To exceed 4,500,000 the second digit must be 6 (the only digit ≥ 5 available). Fix positions 1 and 2 as 4 and 6, then arrange 1, 2, 2, 6, 6 in the last 5 spots: 5! / (1! · 2! · 2!)
When you pick a collection of identical items (or items whose only distinguishing feature is their type) from several categories, you are distributing a count across bins.
Choosing 10 coins from piles of pennies, nickels, dimes, and quarters: let p, n, d, q be the number of each, with p + n + d + q = 10, each ≥ 0. This is a stars-and-bars problem with n = 10 identical stars and k = 4 bins. The answer is C(10 + 4 - 1, 4 - 1) = C(13, 3).
Stars and bars only works when the items within each bin are identical. If you were choosing 10 distinct coins, you would use a different approach.
When you divide n distinct objects into groups of specified sizes and the groups themselves have no labels (they are interchangeable), you compute the multinomial and then divide out the symmetry.
52 cards into 4 unordered piles of 13: start with the multinomial 52! / (13!)⁴, which counts the number of ways to fill pile 1, pile 2, pile 3, pile 4 in order. Since the piles are unordered, divide by 4! to remove the labelling. Result: 52! / ((13!)⁴ · 4!)
52 cards into 3 piles of 8 and 4 piles of 7: the multinomial is 52! / ((8!)³ · (7!)⁴). Divide by 3! for the three interchangeable piles of 8 and by 4! for the four interchangeable piles of 7. Result: 52! / ((8!)³ · (7!)⁴ · 3! · 4!)
Only divide by m! for a group of m piles that share the same size. Piles of different sizes are already distinguishable by their size.
Sum rule: |A ∪ B| = |A| + |B| (when A ∩ B = ∅)
Product rule: |A × B| = |A| · |B|
Combination: C(n, k) = n! / (k!(n - k)!)
Multinomial coefficient: n! / (n₁! · n₂! · ... · nₖ!) where n₁ + n₂ + ... + nₖ = n
Stars and bars: C(n + k - 1, k - 1) for distributing n identical items into k distinct bins
Unordered partition: (multinomial coefficient) / (product of m! for each group of m same-sized piles)
Combinations underpin everything from lottery probability to the design of error-correcting codes. Multinomial coefficients show up in natural language processing when counting word arrangements in a document. Stars and bars is the same maths used to allocate bandwidth, budget, or inventory across departments.
Students often forget to divide by the symmetry factor when piles are unordered. If the problem says "unordered" or "unlabelled," you must divide by m! for each group of m identical-sized piles.
Confusing permutations with combinations: if you are choosing a committee (no roles), use C(n, k). If you are assigning president, vice-president, etc., order matters and you use P(n, k).
Applying stars and bars when items are distinct. Stars and bars counts distributions of identical items. If every item is different, you need a product of combinations or another method.
Forgetting to subtract the repeated-item factorials in the multinomial denominator. Every group of indistinguishable objects contributes a factorial to the denominator.
⚠️ Counting problems are nearly guaranteed on a CS 182 exam. The core skill is recognising which counting tool to use: sum rule vs. product rule vs. combination vs. multinomial vs. stars and bars.
⚠️ Unordered-partition problems (like dealing cards into piles) are a classic exam trap. Always check whether piles are labelled or not.
⚠️ The homework instructions say to give formulas and explain reasoning, not to compute final numbers. That framing is typical of exam questions too: show the setup.
True or False: C(10, 3) = C(10, 7).
Fill in the blank: The number of ways to arrange the letters in "MISSISSIPPI" is 11! / (___).
True or False: Stars and bars can be used to count the number of ways to distribute 5 distinct balls into 3 boxes.
Fill in the blank: To split 20 distinct items into 4 unordered piles of 5, divide the multinomial by ___.
True or False: If you must select 3 items from two groups and both groups must be represented, you sum over the valid splits (1,2) and (2,1).
Q: You have 8 English, 7 French, and 5 German books (all different). How many ways can you select 1 book?
A: 8 + 7 + 5 = 20, by the sum rule.
Q: How many ways to choose a 5-player team from 10 if two specific players must be included?
A: Lock in the 2 required players. Choose the remaining 3 from the other 8: C(8, 3).
Q: How many ways to pick 10 coins from piles of pennies, nickels, dimes, and quarters (unlimited supply)?
A: Stars and bars: C(10 + 4 - 1, 4 - 1) = C(13, 3).
Q: How many distinct arrangements of the digits 1, 2, 2, 4, 6, 6, 6?
A: 7! / (1! · 2! · 1! · 3!) = 420.
Q: 52 cards split into 4 unordered piles of 13. How many ways?
A: 52! / ((13!)⁴ · 4!). The 4! accounts for the piles being unlabelled.
These counting principles feed directly into probability (the next set of study notes): once you can count favourable outcomes and total outcomes, you can compute probabilities. Multinomial coefficients reappear in the binomial and multinomial distributions in probability and statistics. Stars and bars connects to generating functions, a more advanced tool in combinatorics.
counting principles, sum rule, addition principle, product rule, multiplication principle, combination, binomial coefficient, choose function, n choose k, C(n k), multinomial coefficient, permutations with repetition, stars and bars, balls and urns, combinations with repetition, distributing identical objects, partition of a set, unordered partition, labelled vs unlabelled groups, CS 182, CS182, Purdue, foundations of computer science, discrete maths, discrete mathematics, combinatorics