nLab binomial theorem

Redirected from "binomial coefficient".
Contents

Context

Arithmetic

Combinatorics

Contents

Statement

For kk a natural number and rr a complex number, define the falling factorial by

r k̲=r(r1)(rk+1),r^{\underline{k}} = r(r-1)\ldots (r-k+1),

a polynomial of degree kk evaluated at rr. If rr is a natural number, this expression vanishes for k>rk \gt r.

The binomial theorem may be stated thus: if rr is any complex number and |x|<1{|x|} \lt 1, then

(1+x) r= k0r k̲x kk!(1 + x)^r = \sum_{k \geq 0} \frac{r^{\underline{k}} x^k}{k!}

where the left side may be formally defined as exp(rlog(1+x))\exp(r \cdot \log (1+x)), taking the principal branch of the logarithm as defined by the power series

log(1+x)=xx 22+x 33\log(1 + x) = x - \frac{x^2}{2} + \frac{x^3}{3} - \ldots

with radius of convergence equal to 11. (A formal verification of the binomial theorem may be found at coinduction.)

Thus, if we define the binomial coefficient (rk)\binom{r}{k} by the formula

(rk)r k̲k!,\binom{r}{k} \coloneqq \frac{r^{\underline{k}}}{k!},

then we have

(y+x) r= k0(rk)y rkx k(y + x)^r = \sum_{k \geq 0} \binom{r}{k} y^{r-k}x^k

whenever |xy|<1{|\frac{x}{y}|} \lt 1, i.e., whenever |y|>|x|{|y|} \gt {|x|}. More precisely: for any fixed y0y \neq 0, this equation holds for any branch of the logarithm that we use to define (y+x) r(y+x)^r as exp(rlog(y+x))\exp(r\log(y+x)) over the domain {x:|x|<|y|}\{x: {|x|} \lt {|y|}\}.

Combinatorial interpretation

The special finitary case in which i,j,ni, j, n are positive integers,

(i+j) n= 0kn(nk)i kj nk(i + j)^n = \sum_{0 \leq k \leq n} \binom{n}{k} i^k j^{n-k}

may be established combinatorially (or in “bijective fashion”) as follows. Start by interpreting (i+j) n(i + j)^n as the number of functions f:NIJf: N \to I \sqcup J from an nn-element set, where I,JI, J have cardinalities i,ji, j respectively. By pulling back ff along each of the inclusions of I,JI, J into IJI \sqcup J, we get functions f I:f 1(I)If_I: f^{-1}(I) \to I, f J:f 1(J)Jf_J: f^{-1}(J) \to J. Here f 1(I)f^{-1}(I) and f 1(J)f^{-1}(J) are complementary subsets of NN, say of cardinalities kk and nkn-k respectively. (In effect, we are using the fact that the category of finite sets is an extensive category.) Thus, ff determines and is uniquely determined by the following data

  • A subset K(=f 1(I))K (= f^{-1}(I)) of NN,
  • A function g(=f I)g (= f_I) of the form KIK \to I,
  • A function h(=f J)h (= f_J) of the form NKJN-K \to J

and by counting the number of such triplets (K,g,h)(K, g, h), we are led to the right-hand side of the previous displayed equation.

Notice this gives a rigorous proof for the polynomial identity

(x+y) n= 0kn(nk)x ky nk(x+y)^n = \sum_{0 \leq k \leq n} \binom{n}{k} x^k y^{n-k}

since a polynomial in [x,y]\mathbb{Z}[x, y] is the zero polynomial if it vanishes for all positive integer values substituted for xx and yy.

Pascal’s triangle

The binomial coefficient polynomials (xk)\binom{x}{k} (here xx is an indeterminate) satisfy the recurrence

Δ(xk)(x+1k)(xk)=(xk1),(x0)1,(0k)=0(k0)\Delta \binom{x}{k} \coloneqq \binom{x+1}{k} - \binom{x}{k} = \binom{x}{k-1}, \qquad \binom{x}{0} \coloneqq 1, \binom{0}{k} = 0\; (k \neq 0)

where the first two equations may also be written as

Δx k̲k!=x k1̲(k1)!,x 0̲0!=1.\Delta \frac{x^\underline{k}}{k!} = \frac{x^\underline{k-1}}{(k-1)!}, \qquad \frac{x^\underline{0}}{0!} = 1.

The first equation may be viewed as the discrete analogue of the continuous derivative formula

ddxx kk!=x k1(k1)!.\frac{d}{d x} \frac{x^k}{k!} = \frac{x^{k-1}}{(k-1)!}.

The more familiar form of this recurrence,

(x+1k)=(xk)+(xk1),\binom{x+1}{k} = \binom{x}{k} + \binom{x}{k-1},

may be interpreted combinatorially: a kk-element subset KK of X+1X + 1 is either entirely contained in XX, or is determined by the (k1)(k-1)-element subset of XX that is KXK \cap X.

References

See also

Last revised on March 28, 2023 at 00:35:50. See the history of this page for a list of all contributions to it.