Combinations

How many different 5-card poker hands can be dealt from a standard 52-card deck? The answer is not $52 \times 51 \times 50 \times 49 \times 48$ . A hand does not care about the order in which the cards arrived. Only which five cards you end up holding matters. This distinction is between arrangements that count order and selections that ignore it. It is one of the two founding pillars of enumerative combinatorics. The other pillar is Permutations. A combination is precisely an unordered selection of objects from a collection. The central object of study is the count of such selections. It is denoted $\binom{n}{r}$ and called the binomial coefficient. Combinations matter because "how many subsets of size $r$ ?" resurfaces everywhere. Examples include choosing a committee from a group of people. Or choosing which coordinates of a bit string are $1$ . Or choosing which terms survive when you expand $(x+y)^n$ . Or choosing a sample in a probability experiment. The formula for $\binom{n}{r}$ is deceptively simple. But its proof — via the quotient rule linking permutations and combinations — is a template. It applies to a huge swath of combinatorial arguments. You can build a bijection, count the same set two ways, or divide out an overcounting factor. The big picture is this: permutations count ordered selections, combinations count unordered ones. The relationship between them is governed by a clean division. Once $\binom{n}{r}$ is established, an enormous structure opens up. This includes Pascal's triangle, the Binomial Theorem, and symmetric identities. It also includes generalizations like Combinations with Repetition, where objects may be chosen more than once. This article gives the rigorous definition of a combination. It proves the standard formula for $\binom{n}{r}$ two independent ways. It works through nontrivial numerical examples. It also shows exactly which hypotheses are essential by breaking them. These hypotheses include distinctness of objects and no repetition in a selection.

Key takeaways

A combination is an unordered selection of $r$ objects from a set of $n$ distinct objects, i.e., an $r$ -element subset.
The number of $r$ -combinations of an $n$ -set is $\binom{n}{r} = \dfrac{n!}{r!(n-r)!}$ , valid for integers $0 \le r \le n$ .
Combinations differ from Permutations by exactly the factor $r!$ : every subset corresponds to $r!$ ordered arrangements.
$\binom{n}{r} = \binom{n}{n-r}$ (choosing what stays equals choosing what goes) and $\binom{n}{0}=\binom{n}{n}=1$ .
Two independent proofs are given: the quotient-rule (division) proof and a bijective/counting-in-two-ways proof via Pascal's identity.
Key idea: counting unordered selections means counting ordered ones and then dividing by the number of orders each selection admits.

Where this lives today

Combinations are the arithmetic backbone of discrete probability: the probability of drawing a specific hand in card games, a specific configuration in a lottery, or a specific outcome in sampling-without-replacement problems is almost always a ratio of binomial coefficients (hypergeometric distributions). In computer science, $\binom{n}{r}$ governs the running time and correctness analysis of brute-force subset enumeration, feature-selection algorithms in machine learning, and combinatorial optimization bounds. In coding theory and cryptography, binomial coefficients count the number of possible error patterns of a given weight, directly informing the design and analysis of error-correcting codes and the security parameters of code-based cryptosystems. In statistics, $\binom{n}{r}$ is the normalizing count behind the binomial distribution, and in physics, combinations count microstates in statistical mechanics (e.g., the number of ways to place $r$ indistinguishable particles into $n$ distinguishable energy cells subject to exclusion, as in Fermi–Dirac-type counting). The identity $\binom{n}{r} = \binom{n}{n-r}$ and its relatives feed directly into the Binomial Theorem and the broader web of Binomial Identities used throughout generating-function methods.

Ask the tutor: How does $\binom{n}{r}$ become the coefficients in the expansion of $(x+y)^n$ under the Binomial Theorem?

n

Intuition

Think of a permutation as a seating arrangement: you pick $r$ objects and decide the order they occupy $r$ labeled positions. A combination is what remains after you take a photograph of the seating arrangement and then throw away the seat labels — all that survives is who was chosen, not where they sat. Every unordered group of $r$ people can be seated in $r!$ different ordered ways, so the ordered count is exactly $r!$ times the unordered count. This single observation — each unordered outcome is "hit" the same number of times by the ordered counting process — is the quotient rule, and it is the engine behind the formula for $\binom{n}{r}$ . A second useful picture: an $r$ -combination of $\{1, 2, \dots, n\}$ corresponds exactly to a length- $n$ binary string with $r$ ones and $n-r$ zeros (put a $1$ in position $i$ if $i$ is chosen). Counting subsets of size $r$ is the same problem as counting binary strings with $r$ ones — a reformulation that becomes the natural bridge to the Binomial Theorem, where $\binom{n}{r}$ appears as the coefficient of $x^r y^{n-r}$ in $(x+y)^n$ .

Figure

From a 5-set to its 3-subsets: overcounting by order, then dividing by 3! = 6

n, r

P(n,r) = \dfrac{n!}{(n-r)!}

0 \le r \le n

\binom{n}{r} = \frac{n!}{r!(n-r)!}, \qquad \binom{n}{n-r} = \frac{n!}{(n-r)!\,(n-(n-r))!} = \frac{n!}{(n-r)!\,r!}.

n \ge 0

0! = 1

Worked examples

Example 1 — Committee selection with a structural constraint. A university club has $12$ members: $7$ juniors and $5$ seniors. A steering committee of $4$ people is to be chosen, with the requirement that at least $2$ seniors are on the committee. How many such committees are possible? We split into cases by the exact number of seniors, since "at least 2" is not directly a single binomial coefficient — it is a sum over disjoint cases. Case $k=2$ seniors, $2$ juniors: choose which $2$ of the $5$ seniors, and independently which $2$ of the $7$ juniors:

\binom{5}{2}\binom{7}{2} = 10 \cdot 21 = 210.

Case $k=3$ seniors, $1$ junior:

\binom{5}{3}\binom{7}{1} = 10 \cdot 7 = 70.

Case $k=4$ seniors, $0$ juniors:

\binom{5}{4}\binom{7}{0} = 5 \cdot 1 = 5.

These three cases are pairwise disjoint (a committee has a unique number of seniors) and together exhaust all committees with at least $2$ seniors, so by the sum rule the total is

210 + 70 + 5 = 285.

As a check via complementary counting: the total number of $4$ -person committees from $12$ people is $\binom{12}{4} = \frac{12!}{4!\,8!} = 495$ . Committees with fewer than $2$ seniors are those with $0$ or $1$ senior:

\binom{5}{0}\binom{7}{4} + \binom{5}{1}\binom{7}{3} = 1\cdot 35 + 5 \cdot 35 = 35 + 175 = 210.

Then $495 - 210 = 285$ , matching the direct computation exactly.

Example 2 — A lattice path count via a bijection to combinations. How many shortest lattice paths go from $(0,0)$ to $(9,4)$ on the integer grid, moving only right ( $R$ ) or up ( $U)$ one step at a time? Any shortest such path takes exactly $9$ steps of type $R$ and $4$ steps of type $U$ (since the $x$ -coordinate must increase by $9$ total and the $y$ -coordinate by $4$ total, and no step decreases either coordinate). A path is completely determined by choosing, among its $9+4 = 13$ total steps, which $4$ of the $13$ positions are $U$ -steps (the rest are automatically $R$ ). This is exactly an unordered selection of a $4$ -element subset from a $13$ -element set of step-positions — a combination, not a permutation, because swapping which two $U$ -steps occupy which of their chosen positions changes nothing about the resulting string of R's and U's. Hence the number of such paths is

\binom{13}{4} = \frac{13!}{4!\,9!} = \frac{13 \cdot 12 \cdot 11 \cdot 10}{4 \cdot 3 \cdot 2 \cdot 1} = \frac{17160}{24} = 715.

As a sanity check with the symmetry lemma, choosing which $9$ positions are $R$ should give the same count: $\binom{13}{9} = \binom{13}{4} = 715$ , confirming the identity $\binom{n}{r} = \binom{n}{n-r}$ in a nontrivial, asymmetric case ( $9 \ne 4$ ).

\binom{n}{r} = \frac{n!}{r!(n-r)!}

Scope, edge cases & common traps

Situation	Correct handling
$r = 0$	$\binom{n}{0} = 1$ (the empty selection is always available, exactly one way)
$r = n$	$\binom{n}{n} = 1$ (select everything, exactly one way)
$r > n$	$\binom{n}{r} = 0$ by convention; no subset that large exists
Order matters in the problem	Use $P(n,r) = n!/(n-r)!$ , not $\binom{n}{r}$
Objects repeat / selection allows repeats	Use Combinations with Repetition, not this formula
"At least/at most $k$ " constraints	Sum disjoint cases or use complementary counting, never a single binomial coefficient

Common trapThe classic error: silently assuming order doesn't matter, or silently assuming it does

The single most common mistake is choosing between $P(n,r)$ and $\binom{n}{r}$ by pattern-matching keywords ("choose" means combination, "arrange" means permutation) rather than by asking the real question: do two selections that contain the same objects in a different order count as the same outcome or different outcomes? For instance, "how many ways to award gold, silver, and bronze medals to 3 of 10 racers" is a permutation ( $P(10,3) = 720$ ) because swapping who gets gold versus silver produces a genuinely different outcome — even though the word "choose" or "select" might tempt a student toward $\binom{10}{3} = 120$ . Always identify whether the roles/positions in the outcome are distinguishable before selecting a formula.

The mathematician behind it

Origins · 1 minBlaise Pascal and how this was discovered

Blaise Pascal

1623–1662 · 17th-century France, correspondence with Fermat on games of chance

Pascal was a mathematician, physicist, and philosopher whose 1654 correspondence with Pierre de Fermat, prompted by a gambling problem posed by the Chevalier de Méré, is often cited as a founding moment of formal probability theory. Pascal's Traité du triangle arithmétique (1654, published 1665) systematically organized the binomial coefficients into the triangular array now called Pascal's triangle, established the recurrence $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ , and connected the triangle to combinations, probabilities in games of chance, and the coefficients arising in the expansion of $(x+y)^n$ . The triangle and many of its properties had been discovered independently earlier — in India, Persia, and China (notably by Yang Hui and, before him, in the Chandaḥśāstra of Piṅgala) — but Pascal's treatise gave the first fully systematic, proof-based European treatment linking it to combinatorics and probability.

History

- ~200 BCE: Indian mathematician Piṅgala's work on prosody implicitly tabulates binomial-coefficient-like counts.

- 1261 CE: Yang Hui, in China, publishes a triangular array of binomial coefficients (building on the earlier Jia Xian).

- 1654: Pascal and Fermat exchange letters resolving problems of games of chance, laying groundwork for probability.

- 1665: Pascal's Traité du triangle arithmétique is published posthumously, systematizing

\binom{n}{r}

and its triangle.

- 1713: Jacob Bernoulli's Ars Conjectandi further formalizes combinations in the context of probability theory.

What exactly distinguishes a combination from a permutation?

A permutation is an ordered selection: the outcome depends on which objects are chosen and the order/role assigned to each. A combination is an unordered selection: only the set of chosen objects matters, not any order among them. Formally, permutations of $r$ objects from $n$ are counted by tuples with distinct entries, $P(n,r) = n!/(n-r)!$ , while combinations are counted by subsets, $\binom{n}{r} = n!/(r!(n-r)!)$ . Since every $r$ -element subset can be arranged in $r!$ different orders, $P(n,r) = r!\cdot \binom{n}{r}$ always holds — permutations are always at least as numerous as combinations for $r \ge 1$ , and equal only when $r \le 1$ .

Why is

\binom{n}{r}

always an integer, given that its formula involves division?

This follows from the combinatorial meaning: $\binom{n}{r}$ counts an actual finite set of subsets, so it must be a nonnegative integer regardless of how the formula is algebraically simplified. One can also prove integrality directly from Pascal's identity $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ by induction on $n$ , since a sum of two integers is an integer, with base case $\binom{0}{0}=1$ . This gives an independent, purely arithmetic proof of integrality that does not rely on the counting interpretation at all.

Does

\binom{n}{r}

make sense for non-integer or negative

n

The combinatorial definition (counting subsets) requires $n$ to be a nonnegative integer, since it refers to the size of an actual finite set. However, the algebraic expression $\binom{x}{r} = \frac{x(x-1)\cdots(x-r+1)}{r!}$ makes sense for any real or complex $x$ and nonnegative integer $r$ , and this generalized binomial coefficient is exactly what appears in Newton's generalized binomial series. That extension is a separate, purely algebraic construction; it agrees with the combinatorial $\binom{n}{r}$ whenever $x=n$ is a nonnegative integer, but the counting proof given here applies only in that integer regime.

How do combinations relate to the rows of Pascal's triangle?

Row $n$ of Pascal's triangle (starting the count at row $0$ ) lists $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$ in order. The recurrence generating each entry from the row above, $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ , has a direct combinatorial proof: fix one distinguished element $x$ in an $n$ -set; an $r$ -subset either contains $x$ (then choose the remaining $r-1$ elements from the other $n-1$ : $\binom{n-1}{r-1}$ ways) or excludes $x$ (then choose all $r$ elements from the other $n-1$ : $\binom{n-1}{r}$ ways), and these two cases are disjoint and exhaustive.

Can

\binom{n}{r}

be computed without evaluating large factorials directly?

Yes, and this matters for both hand computation and numerical stability. The multiplicative formula

\binom{n}{r} = \frac{n(n-1)\cdots(n-r+1)}{r!}

avoids computing $n!$ and $(n-r)!$ separately as huge intermediate numbers; it only involves $r$ factors in the numerator. Computing terms iteratively (multiply by $(n-i+1)$ , divide by $i$ , at each step $i=1,\dots,r$ ) also guarantees every intermediate quantity stays an integer, since $\binom{n}{i}$ is an integer at every step, which is useful for exact arithmetic in software implementations.

Why does the problem's wording sometimes hide whether it wants a permutation or combination?

Natural language is often ambiguous about whether the roles assigned to selected objects are distinguishable. The safest method is to ask: if I select the same objects but assign them differently (different order, different labels, different positions), is that a new outcome? If yes, use $P(n,r)$ ; if the outcome is identical regardless of internal order, use $\binom{n}{r}$ . Concrete tests help: "choose a committee" (no roles) is a combination; "choose a president and vice-president" (roles attached) is a permutation, even though both use the verb "choose."