Counting, Permutations & Combinations

Counting is rarely about arithmetic first. It is about defining the set of outcomes so precisely that two descriptions cannot denote the same outcome by accident. Once the object is clear—function, injection, subset, bijection, multiset, or orbit—the formula follows from a small number of proof principles.

Count objects, not stories #

For a finite set $X$, its cardinality $|X|$ is the number of elements. The safest way to show two finite families have the same size is a bijection: pair every object in $X$ with exactly one object in $Y$ and vice versa.

This is why the following translations matter:

Here $[r]=\{1,\ldots,r\}$, with $[0]=\varnothing$. This typed view also exposes a common error: when $r<n$, an ordered selection of $r$ objects from an $n$-element set is an injection, not a bijection onto the whole $n$-element set.

Four principles do most of the work #

Disjoint sum rule #

If $A\cap B=\varnothing$, then

$$|A\cup B|=|A|+|B|.$$

The disjointness condition is load-bearing. If outcomes can appear in both cases, adding counts double-counts the intersection; that is the territory of inclusion–exclusion.

For a partition $X=X_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}X_k$,

$$|X|=\sum_{i=1}^k|X_i|.$$

Product rule #

If an outcome is uniquely a pair $(a,b)\in A\times B$, then

$$|A\times B|=|A|\,|B|.$$

For a sequence of stages, multiply the number of legal choices at each stage provided that the stage counts are valid for every preceding partial choice. If later choices depend on earlier ones, the factors may change, but the product rule still applies along each branch.

Complement and subtraction #

If $B\subseteq A$, then

$$|A\setminus B|=|A|-|B|.$$

This is often easier than describing the allowed outcomes directly: count all candidates, then subtract the forbidden set. The subset condition prevents meaningless negative or overlapping subtraction.

Uniform-fiber quotient rule #

Suppose a surjection $q:X\to Y$ maps exactly $k$ objects of $X$ to every $y\in Y$. The fibers partition $X$ into $|Y|$ blocks of size $k$, so

$$|Y|=\frac{|X|}{k}.$$

“Divide by the number of reorderings” is valid only when every abstract outcome has the same number of labelled representations. Nonuniform symmetry groups are the point where naïve division fails.

The two questions that select the formula #

flowchart TD
  start["Choose r items<br/>from n types"]
  order{"Does order matter?"}
  repY{"May a type repeat?"}
  repN{"May a type repeat?"}
  seq["functions<br/>n^r"]
  inj["injections<br/>(n)_r"]
  multi["multisets<br/>C(n+r-1, r)"]
  subset["r-subsets<br/>C(n, r)"]
  start --> order
  order -->|"yes"| repY
  order -->|"no"| repN
  repY -->|"yes"| seq
  repY -->|"no"| inj
  repN -->|"yes"| multi
  repN -->|"no"| subset

The diagram is not a mnemonic detached from meaning. Its four leaves are four different sets: all functions, injections, multisets, and subsets. If a problem mixes labelled roles, indistinguishable items, or equivalence under rotation, first refine the object; do not force it into the nearest leaf.

Ordered choices: powers and falling factorials #

Let $A$ have $n$ elements.

Repetition allowed: $n^r$ #

A length-$r$ sequence is a function $[r]\to A$. Every one of the $r$ positions independently has $n$ choices, hence

$$n^r.$$

This includes the combinatorial convention $n^0=1$: there is exactly one empty sequence, or equivalently one function $\varnothing\to A$. In particular, combinatorics uses $0^0=1$ for the number of empty functions from the empty domain. Other analytic contexts may leave $0^0$ undefined; the counted object resolves the convention here.

No repetition: the falling factorial #

An ordered selection of $r$ distinct items is an injection $[r]\to A$. The first position has $n$ choices, the second $n-1$, and so on:

$$(n)_r=n(n-1)\cdots(n-r+1)=\frac{n!}{(n-r)!}, \qquad 0\le r\le n.$$

If $r>n$, the count is $0$: an injection from a larger finite set into a smaller one cannot exist. The factorial quotient should therefore not be applied outside its stated range.

Permutations are bijections #

If $|A|=n$, a permutation is an ordered selection of all $n$ elements:

$$n!=n(n-1)\cdots2\cdot1.$$

The recursion $n!=n(n-1)!$ says: choose the first image in $n$ ways, then permute the remaining $n-1$ elements. The base case $0!=1$ counts the unique empty bijection $\varnothing\to\varnothing$. Mathlib's factorial documentation points to the formal result that factorial counts permutations, while the NIST DLMF combinatorics chapter records standard permutation and cycle notation.

Cycles expose the mechanism #

A cycle

$$(a_1\ a_2\ \ldots\ a_k)$$

maps $a_1\mapsto a_2,\ldots,a_{k-1}\mapsto a_k,a_k\mapsto a_1$ and fixes all unlisted elements. Repeatedly following $a,\sigma(a),\sigma^2(a),\ldots$ must eventually return to $a$ because $A$ is finite and $\sigma$ is injective. That orbit is one cycle. Starting from an unvisited element and repeating partitions $A$ into disjoint cycles.

Therefore every finite permutation decomposes into disjoint cycles. The decomposition is unique up to:

• rotating the notation inside a cycle, such as $(1\ 3\ 2)=(3\ 2\ 1)$;
• reordering disjoint cycles;
• including or omitting fixed-point $1$-cycles.

Disjoint cycles commute because each fixes every element moved by the other. Overlapping cycles generally do not.

The number of $k$-cycles that can be formed from an $n$-element set, for $1\le k\le n$, is

$$\binom nk(k-1)!=\frac{n!}{k(n-k)!}.$$

Choose the $k$ participants, then arrange them around a directed cycle. There are $k!$ linear listings but each cycle has $k$ rotational listings, leaving $(k-1)!$.

Unordered distinct choices: binomial coefficients #

An $r$-combination from an $n$-element set is an $r$-element subset. Start with the $(n)_r$ ordered selections. Every subset appears in exactly $r!$ orders, so the uniform-fiber rule gives

$$\binom nr =\frac{(n)_r}{r!} =\frac{n!}{r!(n-r)!}, \qquad 0\le r\le n.$$

For $r>n$, define $\binom nr=0$. Formal verification that the $r$-element subsets of an $n$-element finite set have cardinality $\binom nr$ appears as Finset.card_powersetCard in Mathlib's finite-powerset API.

Three identities, three bijections #

Complementing a chosen subset swaps its size from $r$ to $n-r$:

$$\binom nr=\binom n{n-r}.$$

Fix a distinguished element $a$. Every $r$-subset either omits $a$ or contains it:

$$\binom nr=\binom{n-1}r+\binom{n-1}{r-1}.$$

This is Pascal's recurrence, with the two cases disjoint. Finally, partition the whole power set by subset size:

$$2^n=|\mathcal P(A)|=\sum_{r=0}^n\binom nr.$$

The binomial theorem has the same classification. In expanding $(x+y)^n$, choose the $r$ factors that contribute $y$; the other $n-r$ contribute $x$:

$$(x+y)^n=\sum_{r=0}^n\binom nr x^{n-r}y^r.$$

Repeated objects: multinomial coefficients #

Suppose a word of length $n$ contains $m_1$ copies of type 1, …, $m_k$ copies of type $k$, where $m_1+\cdots+m_k=n$. If all copies were temporarily labelled, there would be $n!$ arrangements. Erasing labels within type $i$ identifies exactly $m_i!$ labelled arrangements, independently across types. Thus

$$\binom{n}{m_1,\ldots,m_k}=\frac{n!}{m_1!\cdots m_k!}.$$

Equivalently, choose positions successively:

$$\binom n{m_1} \binom{n-m_1}{m_2}\cdots \binom{m_k}{m_k} =\frac{n!}{m_1!\cdots m_k!}.$$

Unordered choices with repetition: stars and bars #

Choosing a multiset of size $r$ from $n$ labelled types is equivalent to solving

$$x_1+\cdots+x_n=r,\qquad x_i\ge0,$$

where $x_i$ is the multiplicity of type $i$. For $n\ge1$, encode a solution by $r$ stars separated into $n$ bins by $n-1$ bars. Every encoding contains $r+n-1$ symbols, and choosing the $r$ star positions gives

$$\left(\!\!\binom nr\!\!\right) =\binom{n+r-1}{r} =\binom{n+r-1}{n-1}.$$

The left notation denotes multichoose, not an ordinary binomial coefficient. Mathlib formalizes the same identity as Nat.multichoose_eq in its binomial-coefficient library.

If every $x_i$ must be positive, set $y_i=x_i-1\ge0$:

$$x_1+\cdots+x_n=r, x_i\ge1 \quad\Longleftrightarrow\quad y_1+\cdots+y_n=r-n.$$

Hence the count is $\binom{r-1}{n-1}$ when $r\ge n\ge1$, and $0$ when $r<n$.

For $n=0$, the stars-and-bars formula has a negative top index and must not be used. There is one empty multiset when $r=0$, and none when $r>0$.

Circular arrangements and the symmetry trap #

For $n\ge1$ distinct objects around an oriented circle, if rotations count as the same but reflections remain different, there are

$$\frac{n!}{n}=(n-1)!$$

arrangements. Every circular arrangement has exactly $n$ linear representations, one for each choice of starting point.

Mixed constraints: decompose one outcome exactly once #

When a count is uncertain, derive it in two structurally different ways. A mismatch usually reveals either a hidden order, a repeated representation, or overlapping cases.

Computing coefficients without giant factorials #

The factorial formula explains $\binom nr$, but it is a poor numerical algorithm. Use symmetry $k=\min(r,n-r)$ and the exact recurrence

$$\binom n0=1, \qquad \binom ni=\binom n{i-1}\frac{n-i+1}{i} \quad(1\le i\le k).$$

Each step is an integer even though it is written as a product followed by division. In fixed-width code, reduce factors by greatest common divisors or use a big-integer type; computing $n!$ first can overflow long before the final coefficient does.

Pascal's recurrence is preferable when many coefficients for the same $n$ are needed, and dynamic programming over the relevant state definition generalizes naturally to constrained counts. Recurrences and generating functions develop that next layer.

Common counting failures #

A reliable workflow #

1. Define the outcome set, including labels, order, replacement, and equivalence.
2. Check boundary cases: $n=0$, $r=0$, $r>n$, and impossible constraints.
3. Choose a bijection, disjoint partition, Cartesian product, complement, or uniform quotient.
4. Prove that every legal outcome is generated and generated exactly once.
5. Only then simplify the arithmetic.
6. Cross-check with a second decomposition or a small exhaustive enumeration.

The formulas are consequences of this workflow. Memorizing them without their object models is what makes small wording changes so dangerous.