Binomial Coefficient

Given two natural numbers $ n $ and $ k $ with $ 0 \le k \le n $, the binomial coefficient is denoted by $ \binom{n}{k} $, read as "$ n $ choose $ k $". It is defined by the formula \[ \binom{n}{k} = \frac{n!}{k!(n-k)!} \] where "!" denotes the factorial of a natural number and $ 0! = 1 $.

The binomial coefficient is always a natural number and admits two standard interpretations: an algebraic one and a combinatorial one.

Algebraic interpretation

The name "binomial" reflects the fact that as $ k $ runs from $ 0 $ to $ n $, the values $ \binom{n}{k} $ appear exactly as the coefficients in the expansion of the n-th power of a binomial expression $ (a+b)^n $.

\[ (a+b)^n = \sum_{k=0}^{n} \binom{n}{k}\, a^{\,n-k}\, b^{\,k} \]

Each term of the expansion is therefore of the form $ \binom{n}{k} a^{\,n-k} b^{\,k} $. Arranged in a triangular array, these coefficients form the classical Pascal's triangle.

This identity is known as the binomial theorem, which encapsulates the algebraic meaning of the binomial coefficient.

For example, when $ n = 3 $: \[ (a+b)^3 = \binom{3}{0}a^3 + \binom{3}{1}a^2b + \binom{3}{2}ab^2 + \binom{3}{3}b^3 \] Substituting the numerical coefficients: \[ (a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3 \]

Combinatorial interpretation

In combinatorics, the binomial coefficient counts the number of simple combinations $ C_{n,k} $ of size $ k $ that can be selected from a set of $ n $ distinct objects.

\[ C_{n,k} = \binom{n}{k} = \frac{D_{n,k}}{P_k} = \frac{n!}{k!(n-k)!} \]

In other words, it measures how many subsets of size $ k $ can be formed from $ n $ elements when order plays no role.

For instance, choosing 3 members from a committee of 10 people. There are 120 possible selections: \[ \binom{10}{3} = \frac{10!}{3! \cdot 7!} = 120 \] This point of view is fundamental in statistics, probability theory and sampling design.

Properties of the binomial coefficient
Difference between the binomial coefficient and the combinatorial number

Properties of the binomial coefficient

Several important properties are listed below.

Case $ k=0 $
Selecting zero elements from a set of $ n $ elements yields exactly one subset, namely the empty set. $$ \begin{pmatrix} n \\ 0 \end{pmatrix} = 1 $$
Note. Starting from \[ \binom{n}{k} = \frac{n!}{k!(n-k)!} \] substitute $ k = 0 $: \[ \binom{n}{0} = \frac{n!}{0! \cdot n!} = 1 \] since $ 0! = 1 $. The identity $ 0! = 1 $ cannot be established from this formula because that would involve circular reasoning. It must be justified independently.
Case $ k=1 $
Choosing exactly one element from a set of $ n $ elements clearly yields $ n $ possible selections. $$ \begin{pmatrix} n \\ 1 \end{pmatrix} = n $$
Note. Using \[ \binom{n}{1} = \frac{n!}{1!(n-1)!} \] and the identity $ n! = n(n-1)! $, we obtain \[ \binom{n}{1} = n. \]
Case $ k=n $
There is only one way to choose all $ n $ elements: select the entire set. $$ \begin{pmatrix} n \\ n \end{pmatrix} = 1 $$
Note. Substituting $ k=n $ gives \[ \binom{n}{n} = \frac{n!}{n! \cdot 0!} = 1 \] because $ 0! = 1 $.
Case $ n=k=0 $
A set with zero elements has exactly one subset of size zero, again the empty set. $$ \begin{pmatrix} 0 \\ 0 \end{pmatrix} = 1 $$
Note. Using \[ \binom{0}{0} = \frac{0!}{0! \cdot 0!} = 1 \] since $ 0! = 1 $.
Recursive relation (Pascal's identity)
Subsets of size $ k $ drawn from $ n+1 $ elements fall into two disjoint families. Those that exclude the last element, counted by $ \binom{n}{k} $, and those that include it, counted by $ \binom{n}{k-1} $. Together they exhaust all possibilities: \[ \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1} \]
Example. With $ n = 6 $ and $ k = 3 $: \[ \binom{6}{3} = \binom{5}{3} + \binom{5}{2} = 10 + 10 = 20. \]
Symmetry (complementary subsets)
Selecting $ k $ elements from a set of $ n $ is equivalent to selecting the complementary $ n-k $ elements. \[ \binom{n}{k} = \binom{n}{n-k} \] Hence \[ C_{n,k} = C_{n,n-k} = \binom{n}{k}. \] This symmetry is especially useful when $ k > \tfrac{n}{2} $, as it often simplifies calculations.
Example. For $ C_{6,3} $: \[ \binom{6}{3} = \frac{6 \cdot 5 \cdot 4}{3!} = 20. \] Example 2. For $ C_{10,8} $: $$ C_{10,8} = \binom{10}{8} = 45. $$ By symmetry, a faster computation is $$ C_{10,8} = C_{10,2} = \binom{10}{2} = 45. $$ The result is the same, but the second method is more efficient.
Stifel’s Identity
This property, known as Stifel’s identity, states that each binomial coefficient equals the sum of the two coefficients immediately above it in the Pascal's triangle. $$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $$ Stifel’s identity provides a clean recursive approach to computing binomial coefficients, allowing them to be generated efficiently without relying on the factorial formula at every step.
Example. Applying the identity gives $$ \binom{4}{2} = \binom{3}{1} + \binom{3}{2} = 3 + 3 = 6 $$ It can also be expanded recursively within the individual terms: $$ \binom{4}{2} = \binom{3}{1} + \binom{3}{2} $$ $$ \binom{4}{2} = \binom{3}{1} + \underbrace{\binom{2}{1} + \binom{2}{2}}_{\binom{3}{2}} = 3 + 2 + 1 = 6 $$

Difference between the binomial coefficient and the combinatorial number

Formally, $ \binom{n}{k} $ plays two roles:

the binomial coefficient, appearing in the expansion of $ (a+b)^n $,
the combinatorial number, counting the number of $ k $-element subsets of an $ n $-element set.

Symbolically, both interpretations refer to the same quantity:

\[ \binom{n}{k} = \text{binomial coefficient} = \text{number of simple combinations}. \]

They coincide numerically, even though their conceptual origins differ. The distinction reflects the dual algebraic and combinatorial viewpoints.

In practice, they are simply two names for one and the same number.

Binomial coefficient

From the algebraic perspective, the binomial coefficient is the coefficient of $ a^{\,n-k} b^{\,k} $ in the expansion

$$ (a+b)^n = \sum_{k=0}^{n} \binom{n}{k}\, a^{n-k} b^k. $$

Combinatorial number

From the combinatorial perspective, it counts the subsets of size $ k $ that can be chosen from a set of $ n $ elements:

\[ \binom{n}{k} = \text{number of simple combinations } C(n,k). \]

The emphasis here is not on algebraic expansions but on enumerating possible selections.

And so on.