Which counting method do I need?
The decision path from a word problem to the right formula.
Reach for this whenever a probability word problem's denominator (or numerator) is a count you're not sure how to build — ask whether the items are distinct or identical, whether order matters, and how many labeled categories are involved, in that order.
Step 1 — are the items distinct or identical?
Example
Choose this the moment the items being distributed are indistinguishable from each other.
Step 2 — distinct items: does order matter?
Term
permutation
Example
Order matters — arranging, ranking, or awarding distinct roles.
Term
combination
Example
Order doesn't matter — an unranked group or subset.
Example
A special case of "order matters" where the arrangement has no fixed starting point.
Step 3 — more than two labeled categories?
The number of ways to split n distinct items into labeled groups of sizes k_1, k_2, \ldots, k_m (with k_1 + k_2 + \cdots + k_m = n) is \binom{n}{k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!\,k_2!\,\cdots\,k_m!}.
Example
Generalizes a combination to splitting into more than two labeled groups at once.
Show proof
Choose the first group of k_1 items from all n: \binom{n}{k_1} ways. From the n - k_1 that remain, choose the second group of k_2: \binom{n-k_1}{k_2} ways. Continue until every item is placed. By the product rule, the total count is \binom{n}{k_1}\binom{n-k_1}{k_2}\binom{n-k_1-k_2}{k_3}\cdots = \frac{n!}{k_1!(n-k_1)!}\cdot\frac{(n-k_1)!}{k_2!(n-k_1-k_2)!}\cdots. Every factorial in a denominator cancels the matching factorial in the next numerator except the very last, leaving \dfrac{n!}{k_1!\,k_2!\,\cdots\,k_m!}. Setting m=2 recovers the ordinary binomial coefficient \binom{n}{k_1,\,n-k_1} = \binom{n}{k_1}.
Formulas this decision path leads to
The number of ways to arrange r items chosen from n distinct items, where order matters, is P(n,r) = \frac{n!}{(n-r)!}.
Show proof
This is just the counting principle, run r times in a row. The first position in the arrangement can be filled by any of the n items. The second position can be filled by any of the n - 1 items that remain (one has been used). The third by any of the n-2 remaining, and so on, down to the rth position, which has n - (r-1) = n - r + 1 choices left. Multiply across all r positions: P(n,r) = n \cdot (n-1) \cdot (n-2) \cdots (n - r + 1). That product has exactly r factors, starting at n and counting down. To see it equals \frac{n!}{(n-r)!}, write n! in full and notice the tail end cancels: n! = \bigl[n(n-1)\cdots(n-r+1)\bigr] \cdot (n-r)!, so dividing both sides by (n-r)! leaves exactly the product above.
The number of ways to choose r items from n distinct items, where order does not matter, is C(n,r) = \binom{n}{r} = \frac{n!}{r!\,(n-r)!}.
Show proof
Start from P(n,r), which counts every arrangement of r chosen items. Each unordered group of r items corresponds to many of those arrangements — specifically, every one of the r! ways to reorder that same group is a different permutation but the exact same combination. So P(n,r) overcounts each combination by a factor of r!, and dividing it out gives the true count: C(n,r) = \frac{P(n,r)}{r!} = \frac{n!/(n-r)!}{r!} = \frac{n!}{r!\,(n-r)!}.
The number of distinct ways to arrange n distinct items around a circle, where arrangements that differ only by rotation count as the same, is (n-1)!.
Show proof
Line the n items up in a row first: there are n! such arrangements. Bending any one row into a circle produces exactly n different rows that land on the same circular arrangement — one for each rotation of which item is "first." So every circular arrangement is counted n times among the n! linear ones, and dividing removes the overcount: \frac{n!}{n} = (n-1)!. Equivalently: fix one item's seat to remove rotational symmetry, then arrange the other n-1 items in the remaining seats in any order.
The number of ways to split n distinct items into labeled groups of sizes k_1, k_2, \ldots, k_m (with k_1 + k_2 + \cdots + k_m = n) is \binom{n}{k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!\,k_2!\,\cdots\,k_m!}.
Show proof
Choose the first group of k_1 items from all n: \binom{n}{k_1} ways. From the n - k_1 that remain, choose the second group of k_2: \binom{n-k_1}{k_2} ways. Continue until every item is placed. By the product rule, the total count is \binom{n}{k_1}\binom{n-k_1}{k_2}\binom{n-k_1-k_2}{k_3}\cdots = \frac{n!}{k_1!(n-k_1)!}\cdot\frac{(n-k_1)!}{k_2!(n-k_1-k_2)!}\cdots. Every factorial in a denominator cancels the matching factorial in the next numerator except the very last, leaving \dfrac{n!}{k_1!\,k_2!\,\cdots\,k_m!}. Setting m=2 recovers the ordinary binomial coefficient \binom{n}{k_1,\,n-k_1} = \binom{n}{k_1}.
Formula
Stars and Bars
The number of ways to distribute n identical items into k labeled bins (some bins may be empty) is \binom{n+k-1}{k-1}.
Show proof
Represent the n items as n stars in a row. Splitting them into k bins is the same as choosing where to place k-1 dividing bars among the stars — everything before the first bar goes in bin 1, everything between the first and second bar goes in bin 2, and so on. The row now has n stars and k-1 bars, n+k-1 symbols in total, and a distribution is completely determined by which k-1 of those n+k-1 positions hold bars. That is exactly \binom{n+k-1}{k-1} choices.