Binomial coefficient ($\left(\genfrac{}{}{0ex}{}{n}{k}\right)$)

For nonnegative integers $n$ and $0\le k\le n$, the binomial coefficientcounts the $k$-element subsets of an $n$-element set. To obtain the formula, first choose an ordered list of $k$ different members in $n(n-1)\cdots (n-k+1)$ ways. Each subset appears in exactly $k!$ orders, so divide by that factorial. The cases $k=0$ and $k=n$ each have one selection, the empty set and the whole set. For integer $k$ outside $0\le k\le n$, the combinatorial convention is $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$.

For $n=5$, $k=2$, the calculation is $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=5\cdot 4/2=10$. The left-hand panel lists all ten subsets of $\{a,b,c,d,e\}$. Marking an included member with one and an excluded member with zero gives a bijection with length-five binary strings containing exactly two ones. More generally, this makes selection, binary encoding, and coefficients in a binomial theorem three descriptions of the same count.

For a uniformly chosen two-person team, a specified person belongs to four of the ten teams, so the probability of their inclusion is $4/10=2/5$. Uniform selection of a $k$-element subset similarly gives inclusion probability $k/n$ for each member when $n>0$, as the double counting identity shows.

For fixed nonnegative integer $n$, the row $\left(\genfrac{}{}{0ex}{}{n}{0}\right),\dots ,\left(\genfrac{}{}{0ex}{}{n}{n}\right)$ increases to its middle and then decreases. Indeed, for $0\le k<n$, the ratio of consecutive binomial coefficients is $(n-k)/(k+1)$, which is greater than, equal to, or less than $1$ according as $k$ is less than, equal to, or greater than $(n-1)/2$. Thus even $n$ has one maximum at $k=n/2$, while odd $n$ has two equal maxima at $k=(n-1)/2,(n+1)/2$.

For a fixed nonnegative integer $q$, the number of $q$-element subsets of an $n$-element set satisfiesFor $q\ge 1$, divide the product formula for the binomial coefficient by $n^q$:The empty product gives the same result for $q=0$. For an explicit big theta notation bound, $n\ge 2q$ gives $n^q/(2^{q}q!)\le (\genfrac{}{}{0ex}{}{n}{q})\le n^q/q!$. Fixing $q$ is essential: these constants are not uniform when the subset size itself increases with $n$.

Franel sums are sums of fixed powers of binomial coefficients, such as ${\sum }_{k=0}^n{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}^3$.

Choose a $k$-element subset of a disjoint union of sets of sizes $m$ and $n$. Partition the choices by the number $i$ of selected elements from the first set. The resulting count is the displayed convolution of binomial coefficients, where coefficients outside their admissible ranges are zero. This also proves the formula when $k>m+n$.

For $0\le \ell \le k\le n$, count pairs of subsets $L\subseteq K\subseteq X$ with $|X|=n$, $|L|=\ell$ and $|K|=k$. Choosing $K$ before $L$ gives the left product of binomial coefficients. Choosing $L$ and then the $k-\ell$ additional elements of $K$ gives the right product. This double counting proof explains the identity without division by factorials.

For a prime number $p$, the identity $r!\left(\genfrac{}{}{0ex}{}{p}{r}\right)=p(p-1)\cdots (p-r+1)$ has right side divisible by $p$, while $r!$ is coprime to $p$. Cancellation in modular arithmetic proves the divisibility.

// Target: combinatorics.bigb

In polynomial modular arithmetic, prime-row binomial coefficient divisibility gives $(1+X{)}^p\equiv 1+X^p$. Multiply by $(1+X{)}^k$ and compare coefficients of $X^r$ for $r<p$; the $X^p$ term cannot contribute.

// Target: foundations-of-mathematics.bigb

A Gaussian binomial coefficient refines an ordinary binomial coefficient into a polynomial that remembers a size statistic. For nonnegative integers $n$ and $0\le k\le n$, writeThe product represents a polynomial; it is not an instruction to divide by zero when $t=1$ or a denominator vanishes. The Gaussian binomial coefficient recurrence gives a way to compute it with only addition and multiplication. The empty product for $k=0$ is one, and $G_{n,n}(t)=1$ as well. Setting $t=1$ after obtaining the polynomial recovers $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

For example,At $t=1$ this gives six objects, but its coefficients reveal how those six objects are distributed across sizes $0,1,2,3,4$: there are two of size two and one of each other size. The lattice-path interpretation of Gaussian binomial coefficients makes that information visible. Take unit steps north or east from $(0,0)$ to $(2,2)$. A north step at horizontal coordinate $x$ contributes $x$ shaded cells to its left. The six step words have total shaded areas $0,1,2,2,3,4$.

This is useful because an aggregate count can hide the feature one actually wants. A generating function retains the distribution of a statistic, so coefficient extraction answers questions such as “how many allowed diagrams contain exactly two cells?” The partition interpretation of Gaussian binomial coefficients makes every coefficient a nonnegative integer without relying on cancellation in the product formula.

An unexpected second use comes from linear algebra. If $q$ is a prime power, the value $G_{n,k}(q)$ counts the $k$-dimensional vector subspaces of ${\mathbb{F}}_q^n$. Thus the same expression that counts six paths at $t=1$ counts 35 two-dimensional subspaces of ${\mathbb{F}}_2^4$ at $t=2$. The Gaussian binomial coefficient counts finite-field subspaces article explains why selecting a vector subspace differs from selecting a subset of coordinates. ^[ref]

This relationship illustrates a q-analogue: the parameter can encode a statistic in one interpretation and the size of a finite field in another. Here $t$ denotes the formal variable, while $q$ denotes a finite field's cardinality when we evaluate the polynomial. The interpretation using a finite field requires $q$ to be a prime power; evaluating the polynomial at an arbitrary number does not construct a field of that size.

For $n\ge 1$ and $1\le k\le n$, the displayed recurrence relation uses $G_{n,0}(t)=1$ and $G_{n,k}(t)=0$ when $k<0$ or $k>n$. At $t=1$ it becomes Pascal's identity.

An exact weighted-subset formula isThe exponent measures how far the selected positions lie beyond the earliest possible choices $0,\dots ,k-1$. Split the subsets according to whether they contain $n-1$. Those without it give $G_{n-1,k}(t)$; deleting it from those with it removes exactly $n-k$ from their exponent. This gives the displayed recurrence relation, explaining why it builds polynomials with nonnegative integer coefficients.

Use lattice paths with $k$ north steps and $n-k$ east steps, beginning at $(0,0)$. Let $A(P)$ be the sum of the horizontal coordinates of its north steps, equivalently the number of unit cells to their left inside the $k$-by-$(n-k)$ rectangle. A north step in zero-based word position $j_i$ has $i-1$ earlier north steps, so its horizontal coordinate is $j_i-(i-1)$. The Gaussian binomial coefficient recurrence therefore counts these lattice paths with weight $t^{A(P)}$.

For $n=4,k=2$, the words NNEE, NENE, NEEN, ENNE, ENEN, EENN have respective areas $0,1,2,2,3,4$. The word NEEN contributes $t^2$ because the two north steps occur at horizontal coordinates zero and two. These paths never move south or west; allowing such extra steps would change the collection being counted.

The Young diagrams of partitions in a rectangle with at most $k$ rows and at most $n-k$ cells in each row correspond to the lattice paths in the lattice-path interpretation of Gaussian binomial coefficients. Read the shaded row lengths from top to bottom; the result is a nonincreasing list of nonnegative integers. This bijection preserves the number $|\lambda |$ of cells.

In a two-by-two rectangle, the possibilities are the empty integer partition, $(1)$, $(2)$, $(1,1)$, $(2,1)$, and $(2,2)$. Their sizes are $0,1,2,2,3,4$, giving $G_{4,2}(t)$. In particular, there are two allowed diagrams of size two, explaining the middle coefficient.^[ref]

Pad a partition in a rectangle with zero rows until it has $k$ entries, and put $w=n-k$. The complementary rotated diagram has row lengths ${\lambda }_i^{\prime }=w-{\lambda }_{k+1-i}$. This is again a partition in a rectangle, and its size is $kw-|\lambda |$. Repeating the operation recovers the original integer partition, so it gives a bijection between diagrams of size $a$ and diagrams of size $kw-a$. Consequently the coefficients of the Gaussian polynomial read the same in either direction. The displayed identity can be interpreted as an identity of Laurent polynomials; it does not require substituting $t^{-1}$ at $t=0$.

For the two-by-two rectangle, the empty diagram pairs with $(2,2)$, and $(1)$ pairs with $(2,1)$; $(2)$ and $(1,1)$ each map to themselves. This establishes symmetry, while unimodality of Gaussian binomial coefficients is a stronger statement about the growth and decrease of successive coefficients.

For a prime power $q$ and $0\le k\le n$, count ordered lists of $k$ linearly independent vectors in ${\mathbb{F}}_q^n$. The first has $q^n-1$ choices. After $i$ independent choices, their linear span contains $q^i$ vectors, so the next has $q^n-q^i$ choices. Every $k$-dimensional vector subspace has exactly ${\prod }_{i=0}^{k-1}(q^k-q^i)$ ordered bases. Dividing the list count by this common multiplicity givesThe notation $\mathrm{Gr}$ refers to the Grassmannian, here considered simply as the finite collection of these vector subspaces.^[ref]

For $n=4,k=2,q=2$, there are $15\cdot 14=210$ ordered independent pairs. Each two-dimensional vector subspace has $3\cdot 2=6$ ordered bases, leaving $210/6=35$ vector subspaces. There are only $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ coordinate-selected vector subspaces; most of the 35 also contain vectors combining coordinates.

A unique reduced row echelon form gives another count. Its six possible pivot-column patterns have $4,3,2,2,1,0$ freely chosen entries. Each free entry lies in ${\mathbb{F}}_2$, giving $16,8,4,4,2,1$ vector subspaces, respectively. The diagram fixes the zero entries required to make each pivot the first nonzero entry in its row and the only nonzero entry in its column. Different choices describe different row spaces.

For $0\le k\le n$, let $V$ be the $n$-dimensional irreducible sl2 Lie algebra representation. Its weights are $n-1,n-3,\dots ,1-n$. A wedge basis shows $\mathrm{ch}{\Lambda }^{k}V=q^{-k(n-k)}{G}_{n,k}(q^2)$, where $G_{n,k}(t)$ is the Gaussian binomial coefficient. By the Weyl complete reducibility theorem, this character is a nonnegative sum of irreducible strings $q^m+q^{m-2}+\cdots +q^{-m}$. All its weights have parity $k(n-k)$, so their coefficients increase toward zero and decrease afterward. Consequently the coefficients of $G_{n,k}(t)$ are symmetric and unimodal. The symmetric quantum binomial coefficient is this character, a Laurent polynomial; its coefficients are unimodal on the occupied parity. The full integer-exponent sequence need not be unimodal, as $q+q^{-1}$ demonstrates.

The quotient $[n{]}_q[n-1{]}_q\cdots [n-k+1{]}_q/([k{]}_q\cdots [1{]}_q)$ is the displayed shifted Gaussian binomial coefficient. It is the formal character of ${\Lambda }^k{L}_{n-1}$, where $L_{n-1}$ is the $n$-dimensional irreducible sl2 Lie algebra representation. Indeed its exterior-power weights are sums of $k$ distinct terms of $n-1,n-3,\dots ,1-n$. Parity unimodality of an sl2 character proves unimodality after removing the intervening zero coefficients; equivalently, the ordinary Gaussian polynomial has unimodal coefficients.

Row $n$ of Pascal's triangle consists of the binomial coefficients $\left(\genfrac{}{}{0ex}{}{n}{0}\right),\dots ,\left(\genfrac{}{}{0ex}{}{n}{n}\right)$, beginning with row $0$. Boundary entries are one, and Pascal's identity says each interior entry is the sum of the two entries above it. The hockey-stick identity evaluates sums along its diagonals.

The highlighted entry in the binomial coefficient illustration is $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$. Split two-person teams according to whether they contain the fifth person: six choose both members from the other four, and four contain the fifth person together with one of those four. Thus $10=6+4$. All entries can be generated by the same local rule, so a large table of counts needs no repeated enumeration of its subsets.

Reading row seven. Label the entries in each row from $k=0$ on the left through $k=n$ on the right. Rows zero through seven are shown below. The highlighted entry $T_{7,3}=35$ comes from $T_{6,2}=15$ and $T_{6,3}=20$. Starting with row zero $(1)$, the edges remain one and Pascal's rule determines every interior entry, so mathematical induction uniquely determines the whole array.

The triangular and rectangular layouts describe the same entries. For a north-east lattice path ending at $(a,b)$, set $n=a+b$ and $k=b$, so $P(a,b)=T_{n,k}$. The predecessor $(a-1,b)$ has indices $(n-1,k)$, while $(a,b-1)$ has indices $(n-1,k-1)$. Thus the grid's west and south arrivals are exactly the triangle's two parents. This change of indices explains why the north-east lattice path recurrence and Pascal's rule agree.

There is also a global check on the local construction: row $n$ sums to $2^n$. Every subset of an $n$-element set appears exactly once among the classes of sizes $0,\dots ,n$, and each element has two inclusion choices by the rule of product. In row seven, $1+7+21+35+35+21+7+1=128=2^7$. Replacing every subset by its complement reverses the row, explaining $T_{n,k}=T_{n,n-k}$. The binomial theorem packages the whole row as the coefficients of $(1+x{)}^n$.

Blaise Pascal's Traité du triangle arithmétique, published in 1665, presents an arithmetic array and connects it to combinations, games of chance, and powers of binomial expressions. This makes the connection between a counting table and several applications visible in the original work. ^[ref] The University of Cambridge's account of the treatise explains its 1654 composition and the organization of these applications. ^[ref]

For nonnegative integers $n,m$, the binomial coefficients satisfyThe identity follows by mathematical induction: adding the next term combines two adjacent binomial coefficients through Pascal's identity. An equivalent form is ${\sum }_{r=j}^N\left(\genfrac{}{}{0ex}{}{r}{j}\right)=\left(\genfrac{}{}{0ex}{}{N+1}{j+1}\right)$, a diagonal sum in Pascal's triangle. It provides closed forms for sums of binomial coefficients without expanding individual factorials.

For a prime number $p$, the binomial coefficient modulo $p$ factors into the corresponding digit binomial coefficients in the base-p expansions of the nonnegative integers $n,k$. Pad both expansions to the same length and use $\left(\genfrac{}{}{0ex}{}{a}{b}\right)=0$ when $b>a$. The identity follows by factoring $(1+x{)}^n$ into digit powers and using the Frobenius endomorphism; digit uniqueness identifies each coefficient.

For a prime number $p$ and integer $r\ge 1$, every interior binomial coefficient in row $p^r$ is divisible by $p$. The polynomial identity $(1+x{)}^p\equiv 1+x^p(\mathrm{mod}p)$ iterates under the Frobenius endomorphism to $(1+x{)}^{p^r}\equiv 1+x^{p^r}(\mathrm{mod}p)$. This concerns divisibility by $p$, not necessarily by $p^r$.

For a positive integer $N$, all binomial coefficients $\left(\genfrac{}{}{0ex}{}{N}{j}\right)$ with $0<j<N$ are even exactly when $N$ is a power of two. Write the binary expansion $N={\sum }_{i\in I}{2}^i$. In the polynomial ring ${\mathbb{F}}_2[t]$, repeated squaring givesIf $I$ has one element, there are no interior terms. If it has more than one, the coefficient of $t^{2^{\min I}}$ is one and that exponent lies strictly between zero and $N$. This characterization gives a useful parity obstruction directly from the binary expansion.

Every positive integer $m$ has a unique greedy representationThis is also called the binomial representation of $m$ at level $r$.

Pascal's identity is

For an integer $n\ge 1$ and any integer $k$, Pascal's rule holds with the convention $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$ outside $0\le k\le n$. The boundary values are $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=\left(\genfrac{}{}{0ex}{}{n}{n}\right)=1$, including $\left(\genfrac{}{}{0ex}{}{0}{0}\right)=1$. Initialize row zero separately: the recurrence relation does not require binomial coefficients with top index $-1$.^[ref]

Proof by a marked element. Count the $k$-element subsets of $\{1,\dots ,n\}$, marking the element $n$ as special. Those omitting $n$ are exactly the $k$-element subsets of $\{1,\dots ,n-1\}$. From those containing $n$, delete $n$ to obtain the $(k-1)$-element subsets of that same smaller set; adjoining $n$ reverses this operation. The rule of sum adds these two disjoint counts. The proof includes $k=0$ and $k=n$ because the impossible class contributes zero.

For an original worked instance, choose three labels from $\{1,2,3,4,5,6,7\}$ and mark $7$. Omitting it gives $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ selections. Including it leaves two labels to choose from the other six, giving $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$. Therefore $\left(\genfrac{}{}{0ex}{}{7}{3}\right)=20+15=35$. Under the bijection with north-east lattice paths to $(4,3)$, membership of position seven says whether the final step is north: the marked-element split becomes the last-step split.

This makes Pascal's rule useful beyond an algebraic identity. A counting problem may have an obvious yes-or-no decision even when its factorial formula is obscure; splitting at that decision exposes a recurrence relation. When the smaller counts are shared between many cases, dynamic programming reuses them. The beauty of Pascal's triangle is that one local addition rule simultaneously organizes subsets, binary strings, north-east lattice paths, and the binomial theorem.

The central binomial coefficient is the largest coefficient in the expansion of $(1+1{)}^{2n}$:

Set $c_n=4^{-n}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$, with $c_0=1$. Cancellation of factorials givesConsequently $c_n$ decreases to zero: $\log c_n\le -\frac{1}{2}{\sum }_{j=1}^{n}1/j\le -\frac{1}{2}\log (n+1)$. The inequality uses $\log (1-x)\le -x$ and comparison with ${\int }_1^{n+1}dt/t$. Conversely $c_n\ge 1/(n+1)$ by induction, since its ratio is at least $(n+1)/(n+2)$. Thus $\sum c_n$ diverges while $\sum (-1{)}^n{c}_n$ has conditional convergence by the alternating series test. These elementary bounds require no asymptotic formula for factorials.

For nonnegative integers with $n_1+\cdots +n_r=n$, the multinomial coefficientcounts arrangements of a multiset containing $n_j$ copies of symbol $j$.

For a nonnegative integer $n$,

For a nonnegative integer $n$ and commuting quantities $x,y$,In expanding the $n$ factors, obtain $x^k{y}^{n-k}$ by selecting the $k$ positions that contribute $x$. There are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ such choices. For example,The coefficients are row five of Pascal's triangle, in reverse order under the displayed $x^k{y}^{n-k}$ convention; the row is symmetric. Setting $x=y=1$ gives $1+5+10+10+5+1=32$, the number of subsets of a five-element set. Each member has two inclusion choices, agreeing with the rule of product and the cardinality of the power set.

The binomial expansion expresses $(a+b{)}^n$ as ${\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)a^{n-k}{b}^k$ for a nonnegative integer $n$. The binomial coefficients give the number of ways to choose which $k$ factors supply $b$.

These two finite-sum transformations are inverses over any commutative ring. Substitute one sum into the other and use $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\left(\genfrac{}{}{0ex}{}{k}{j}\right)=\left(\genfrac{}{}{0ex}{}{n}{j}\right)\left(\genfrac{}{}{0ex}{}{n-j}{k-j}\right)$. The inner alternating sum is $(1-1{)}^{n-j}$ by the binomial theorem, so only $j=n$ survives. In a Mahler expansion, $b_n$ is the nth finite difference of the sampled values $a_k$.

For nonnegative integers $r,n$, the alternating binomial moment satisfies $S_r(n)=0$ when $r<n$ and $S_n(n)=(-1{)}^{n}n!$. Expand the polynomial $X^r$ in falling factorials and differentiate the binomial theorem to prove these identities. Equivalently, alternating binomial coefficients implement a finite difference that annihilates polynomials of degree less than $n$.

In a commutative ring of characteristic $p$,Iteration gives $(x+y{)}^{p^n}=x^{p^n}+y^{p^n}$.

If square matrices $A$ and $B$ commute, thenThe usual proof works because commutativity allows words with the same numbers of $A$ and $B$ factors to be collected.

Coefficient extraction from $(1-x{)}^n(1+x{)}^n=(1-x^2{)}^n$ gives