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

The binomial coefficientcounts the $k$-element subsets of an $n$-element set. Equivalently, it counts strings containing $k$ copies of one symbol and $n-k$ copies of another.

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.

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

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

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$,

Combinatorics studies finite and discrete structures through counting, construction, and extremal arguments.

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