Combinatorial Probability

How likely are you to be dealt a full house in poker? What is the chance that among twenty-three strangers, two share a birthday? Questions like these seem to be about cards and calendars. But underneath they are all the same question. Out of a finite universe of equally plausible outcomes, what fraction belongs to the event we care about? Combinatorial probability is the systematic answer to that question. It is built on the idea of counting rather than measuring. The idea matters because it is the bridge between two things. On one side is the abstract The Axioms of Probability, which only guarantee that probabilities are consistent numbers. On the other side is the concrete arithmetic that lets us actually compute them. When a sample space is finite and every outcome is equally likely, probability collapses into a counting problem. Divide the number of favorable outcomes by the total number of outcomes. The entire difficulty, and the entire richness, of the subject then lies in counting correctly. This is where permutations, combinations, and their many variants enter. The big picture is that "equally likely outcomes" is not a universal law of nature. It is a modeling choice. This choice is exactly right for idealized dice, cards, and coins. Its careless application is also the single most common source of probability errors. Once the model is fixed, however, the classical definition of probability simplifies things greatly. It turns every probability computation into two counting computations: count the favorable outcomes, count all outcomes, divide. This article gives the precise definition of the classical (equally-likely-outcomes) probability model. It develops the counting tools — permutations, combinations, and the multiplication principle — needed to apply it. It proves the central formula rigorously from the axioms. It also works through genuinely asymmetric examples, a poker hand and a birthday-type collision problem, to show the machinery in full force. It closes by showing exactly where the "equally likely" hypothesis can fail. Finally, it shows where combinatorial probability leads next: toward Conditional Probability and toward Discrete Random Variables built from these same counts.

Key takeaways

Combinatorial probability applies when a sample space is finite and every outcome is equally likely.
In that model, $P(A) = |A|/|S|$ : probability is literally a ratio of counts.
The multiplication principle is the engine underneath every counting formula.
Permutations count ordered selections; combinations count unordered selections.
Classic applications: card hands, birthday coincidences, lottery-style draws, sampling without replacement.
Key idea: when outcomes are symmetric, probability is a counting problem in disguise.

Where this lives today

Combinatorial probability is the computational backbone of elementary probability theory and reaches far beyond games of chance. In cryptography, the security of many schemes rests on counting: the probability of guessing a key by brute force, or of a hash collision, is a ratio of favorable to total equally likely bit-strings, directly generalizing the birthday-collision calculation above. In statistics, the hypergeometric distribution — describing sampling without replacement from a finite population, as in quality control or ecological capture-recapture studies — is built entirely from combinations $\binom{n}{r}$ . In computer science, algorithm analysis for randomized algorithms (random pivoting in quicksort, hashing schemes, randomized load balancing) uses exactly the permutation/combination counting developed here to bound expected running times and collision probabilities. In physics, statistical mechanics computes the entropy and equilibrium behavior of systems (e.g., counting microstates of gas particles in a box) using the same combinatorial counting of equally likely microstates, going back to Boltzmann's counting-based definition of entropy. In genetics, Punnett-square and allele-combination calculations are direct applications of the multiplication principle and combinations to equally likely gamete pairings. Within probability itself, this machinery is the immediate precursor to Conditional Probability (where counting is restricted to a reduced sample space) and to building Discrete Random Variables such as the binomial and hypergeometric distributions, whose probability mass functions are literally combinatorial counting formulas normalized to sum to one.

Ask the tutor: Can you walk me through why the full-house count uses 12 remaining ranks but not 11, and how that connects to conditional counting?

S

Intuition

Picture the sample space $S$ as a finite collection of points, all drawn the same size because none is favored over another — that is exactly what "equally likely" means geometrically. An event $A$ is simply a subset of these points. Since the axioms of probability require $P$ to be additive over disjoint outcomes and to total $1$ over the whole space, and since the equally-likely hypothesis forces every point to carry the same weight, that weight must be $1/N$ ; the probability of $A$ is then just the fraction of the space that $A$ occupies. This is the entire content of the classical model — the rest of the subject is about counting the points correctly. The subtlety is almost always about order. Suppose you draw two balls from a bag of $5$ distinct balls. If you record which ball came first and which came second, you are counting ordered pairs, and there are $P(5,2) = 20$ of them. If you only care which two balls ended up in your hand, you are counting unordered pairs, and there are $\binom{5}{2} = 10$ of them. Both are legitimate sample spaces for the "same" physical experiment, and both give equally-likely outcomes under uniform random drawing — the trap is mixing the two, e.g., counting favorable outcomes as unordered while counting the total sample space as ordered, or vice versa. The picture below shows this ordered/unordered duality directly: the $20$ arrows correspond to ordered draws, and grouping each arrow with its reverse produces the $10$ unordered pairs.

Figure

Ordered draws (arrows) versus unordered pairs (undirected edges) among 5 balls

The central theorem

S

A

A, B \subseteq S

Worked examples

Example 1: A poker hand (asymmetric event, unordered sampling). A standard deck has $52$ distinct cards: $13$ ranks (2 through 10, J, Q, K, A) in each of $4$ suits. A poker hand is a uniformly random $5$ -card subset of the deck (order of dealing is irrelevant to the hand held). We compute the probability of a full house: three cards of one rank and two cards of a different rank (e.g. $3\clubsuit\,3\diamondsuit\,3\heartsuit\,Q\spadesuit\,Q\clubsuit$ ). Sample space size. Since a hand is an unordered $5$ -subset of $52$ cards,

N = \binom{52}{5} = \frac{52!}{5!\,47!} = 2{,}598{,}960.

Favorable count, via the multiplication principle applied to independent stages of the construction of a full house: 1. Choose the rank to be used three times: $13$ ways (any of the $13$ ranks). 2. Choose which $3$ of the $4$ suits in that rank appear: $\binom{4}{3} = 4$ ways. 3. Choose the rank to be used twice, which must differ from the rank chosen in step 1: $12$ remaining ranks. 4. Choose which $2$ of the $4$ suits in that second rank appear: $\binom{4}{2} = 6$ ways. These four stages are independent choices (the option count at each stage does not depend on which specific option was chosen earlier, only on how many choices remain), so by the multiplication principle the number of full houses is

|A| = 13 \times \binom{4}{3} \times 12 \times \binom{4}{2} = 13 \times 4 \times 12 \times 6 = 3{,}744.

Probability.

P(\text{full house}) = \frac{3{,}744}{2{,}598{,}960} = \frac{6}{4165} \approx 0.001441.

A common error here is to choose the pair rank before the triple rank and multiply by an extra factor of $2$ for "which rank is which" — but the four-stage construction above already distinguishes the triple-rank stage from the pair-rank stage (they use different binomial coefficients, $\binom{4}{3}$ versus $\binom{4}{2}$ , and different remaining-rank counts, $13$ versus $12$ ), so no such correction is needed; each full house is generated by exactly one sequence of choices in this scheme.

Example 2: A collision (matching) problem — asymmetric group sizes. A company has $10$ interview slots in a day, filled independently and uniformly at random by assigning each of $10$ candidates to one of $30$ available time slots (assume $30 \ge 10$ so an injective assignment is possible, and every candidate's slot choice is unconstrained by the others, i.e., we first ask: what is the probability that no two candidates are assigned the same slot — a "no-collision" event that is the natural generalization of the birthday problem, here with $30$ "days" instead of $365$ and $10$ "people" instead of a class of students? Sample space. Each of the $10$ candidates independently picks one of $30$ slots. By the multiplication principle (10 independent stages, each with $30$ options),

N = 30^{10}.

Favorable event: all 10 slots distinct. Build an injective assignment stage by stage: candidate $1$ can take any of $30$ slots; candidate $2$ must avoid candidate $1$ 's slot, leaving $29$ options; candidate $3$ must avoid the $2$ already taken, leaving $28$ ; and so on, down to candidate $10$ , who has $30 - 9 = 21$ options. This is exactly the ordered-selection (permutation) count $P(30,10)$ :

|A| = P(30,10) = 30 \times 29 \times 28 \times \cdots \times 21 = \frac{30!}{20!}.

Probability of no collision.

P(\text{all distinct}) = \frac{30 \cdot 29 \cdot 28 \cdots 21}{30^{10}}.

Numerically, computing the product of ratios $\frac{30-j}{30}$ for $j = 0, \dots, 9$ :

\prod_{j=0}^{9}\left(1 - \frac{j}{30}\right) \approx 1.000 \times 0.9667 \times 0.9333 \times 0.9000 \times 0.8667 \times 0.8333 \times 0.8000 \times 0.7667 \times 0.7333 \times 0.7000.

Multiplying these ten factors successively gives

P(\text{all distinct}) \approx 0.1400.

Hence the probability of at least one collision — two candidates sharing an interview slot — is

P(\text{collision}) = 1 - P(\text{all distinct}) \approx 1 - 0.1400 = 0.8600,

using the complement corollary above. Despite there being $30$ slots and only $10$ candidates (fewer than a third), a collision is quite likely — the same surprising phenomenon responsible for the classical birthday paradox, now verified with fully asymmetric numbers ( $30$ , not $365$ ; $10$ , not $23$ ) rather than the textbook-special case.

P(\{s\}) = 1/N

Scope, edge cases & common traps

Situation	Correct treatment
Sampling without replacement, order matters	Use $P(n,r)$ for both favorable and total counts
Sampling without replacement, order irrelevant	Use $\binom{n}{r}$ consistently in numerator and denominator
Sampling with replacement	Use the multiplication principle directly ( $n^r$ total outcomes), not $\binom{n}{r}$ or $P(n,r)$
Objects are not all distinguishable (e.g. identical items)	Adjust the sample space definition itself before counting, or count via distinguishable labels and then check whether outcomes are truly equally likely
Outcomes are physically or empirically unequal (biased die, loaded coin, non-uniform population)	The classical formula does not apply; use direct additivity with the actual point probabilities instead

The mathematician behind it

Origins · 1 minJacob Bernoulli and how this was discovered

Jacob Bernoulli

1655–1705 · Basel, Switzerland — the mathematical treatment of chance from games and urns

Jacob Bernoulli was a member of the Bernoulli family of mathematicians in Basel and one of the founders of the mathematical theory of probability. His treatise Ars Conjectandi ("The Art of Conjecturing"), published posthumously in 1713, systematized the combinatorial analysis of games of chance — permutations, combinations, and the counting of equally likely outcomes — and used it to prove the first version of the Law of Large Numbers, connecting finite combinatorial counting to long-run frequency. His work built directly on, and made rigorous, the informal dice-and-cards reasoning of Cardano, Pascal, and Fermat.

History

- 1654 — Pascal and Fermat correspond on the "problem of points," analyzing games of chance combinatorially.

- 1657 — Huygens publishes De Ratiociniis in Ludo Aleae, the first printed treatise on probability, based on counting equally likely cases.

- 1713 — Bernoulli's Ars Conjectandi is published posthumously, formalizing permutations, combinations, and the equally-likely-outcomes model.

- 1812 — Laplace's Théorie Analytique des Probabilités gives the classical definition of probability as a ratio of favorable to total equally possible cases.

- 1933 — Kolmogorov's axiomatization places the classical (equally likely) model as one special case within a fully general measure-theoretic framework.

Why does P(A) = |A|/N require every outcome to be equally likely, rather than just requiring the sample space to be finite?

Finiteness alone only guarantees that $A$ decomposes into finitely many disjoint singletons, so by additivity $P(A) = \sum_{s \in A} P(\{s\})$ . That sum equals $|A|/N$ only if each term $P(\{s\})$ equals the constant $1/N$ . If the outcomes carry different weights — as with a loaded die — the sum still makes sense but does not simplify to a ratio of counts; you must add the actual (unequal) probabilities. The The Axioms of Probability guarantee consistency of any valid assignment of weights, equal or not, but they do not by themselves force equal weights — that is a separate physical or modeling assumption about the experiment.

When should I use permutations P(n,r) versus combinations C(n,r) in a probability computation?

Use $P(n,r)$ whenever the order in which objects are selected or arranged is part of what defines an outcome — for example, the sequence of finishers in a race, or an ordered hand of cards dealt one at a time and recorded in order. Use $\binom{n}{r}$ whenever only the set of selected objects matters, with no attached order — a poker hand held in your fingers, a committee, a lottery ticket's numbers. The critical rule is consistency: whichever convention you choose for counting favorable outcomes, you must use the identical convention for counting the total sample space, or the ratio will be wrong.

Does "sampling without replacement" always mean I should use combinations?

Not necessarily — it depends on whether the resulting outcome records order. Sampling without replacement rules out repeats, but you can still record the order of the draws (giving $P(n,r)$ ) or discard the order and keep only the resulting set (giving $\binom{n}{r}$ ). Both are valid without-replacement models; the poker hand example uses combinations because a hand is a set of cards, while the interview-slot example uses permutations because each candidate is a distinguishable individual assigned to a distinguishable slot, so which candidate got which slot matters.

How does the classical model relate to the general axiomatic definition of probability?

The classical (equally likely outcomes) model is a special case of the general axiomatic framework in The Axioms of Probability, not a replacement for it. The axioms require only that $P$ be nonnegative, assign total mass $1$ to $S$ , and be countably additive over disjoint events; they say nothing about how the mass is distributed among individual outcomes. The classical model is the extra modeling choice of distributing that mass uniformly across a finite $S$ . Every classical probability computation is fully justified, and only justified, by the general axioms plus this uniformity assumption, exactly as proved in the central theorem here.

Why does the "birthday problem" style calculation give such a counterintuitive answer?

The surprise comes from comparing the wrong two quantities: it feels like $10$ candidates among $30$ slots should rarely collide because $10$ is much less than $30$ . But the number of pairs of candidates who could potentially collide grows quadratically, as $\binom{10}{2} = 45$ pairs, while the number of slots grows only linearly. The probability of avoiding all collisions is a product of many factors each slightly less than $1$ , and such a product shrinks faster than intuition suggests — this is a purely combinatorial phenomenon, not a paradox, and the exact computation in the worked example makes it precise rather than merely plausible.

Can the equally-likely-outcomes model be used when the sample space is infinite?

No — not directly, and this is a fundamental limitation, not a minor technicality. If $S$ is countably infinite and every outcome had the same probability $p > 0$ , countable additivity would force $\sum_{s \in S} P(\{s\}) = \infty \cdot p$ , which cannot equal $1$ for any $p > 0$ ; taking $p = 0$ gives total mass $0$ , not $1$ , again violating the requirement that $P(S) = 1$ . So a countably infinite sample space cannot have all outcomes equally likely. Continuous analogues (uniform distributions on an interval) exist but require measure theory beyond simple counting, and are a distinct construction built on top of, not identical to, the classical discrete model.

What is the single most useful habit for avoiding errors in combinatorial probability?

Explicitly write down the sample space $S$ as a set of well-defined outcomes — ordered tuples or unordered sets, precisely stated — before computing anything. Then define the event $A$ as a subset of that same $S$ , using the same ordered/unordered convention. Only after both are pinned down should you invoke the multiplication principle, $P(n,r)$ , or $\binom{n}{r}$ to count each. Most classic combinatorial-probability mistakes come from computing $|A|$ and $|S|$ against two different implicit sample spaces, which the formula $P(A)=|A|/N$ silently assumes to be the same space.