transfinite arithmetic, cardinal arithmetic, ordinal arithmetic
prime field, p-adic integer, p-adic rational number, p-adic complex number
arithmetic geometry, function field analogy
Basic structures
Generating functions
Proof techniques
Combinatorial identities
Polytopes
For $k$ a natural number and $r$ a complex number, define the falling factorial by
a polynomial of degree $k$ evaluated at $r$. If $r$ is a natural number, this expression vanishes for $k \gt r$.
The binomial theorem may be stated thus: if $r$ is any complex number and ${|x|} \lt 1$, then
where the left side may be formally defined as $\exp(r \cdot \log (1+x))$, taking the principal branch of the logarithm as defined by the power series
with radius of convergence equal to $1$. (A formal verification of the binomial theorem may be found at coinduction.)
Thus, if we define the binomial coefficient $\binom{r}{k}$ by the formula
then we have
whenever ${|\frac{x}{y}|} \lt 1$, i.e., whenever ${|y|} \gt {|x|}$. More precisely: for any fixed $y \neq 0$, this equation holds for any branch of the logarithm that we use to define $(y+x)^r$ as $\exp(r\log(y+x))$ over the domain $\{x: {|x|} \lt {|y|}\}$.
The special finitary case in which $i, j, n$ are positive integers,
may be established combinatorially (or in “bijective fashion”) as follows. Start by interpreting $(i + j)^n$ as the number of functions $f: N \to I \sqcup J$ from an $n$-element set, where $I, J$ have cardinalities $i, j$ respectively. By pulling back $f$ along each of the inclusions of $I, J$ into $I \sqcup J$, we get functions $f_I: f^{-1}(I) \to I$, $f_J: f^{-1}(J) \to J$. Here $f^{-1}(I)$ and $f^{-1}(J)$ are complementary subsets of $N$, say of cardinalities $k$ and $n-k$ respectively. (In effect, we are using the fact that the category of finite sets is an extensive category.) Thus, $f$ determines and is uniquely determined by the following data
and by counting the number of such triplets $(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
since a polynomial in $\mathbb{Z}[x, y]$ is the zero polynomial if it vanishes for all positive integer values substituted for $x$ and $y$.
The binomial coefficient polynomials $\binom{x}{k}$ (here $x$ is an indeterminate) satisfy the recurrence
where the first two equations may also be written as
The first equation may be viewed as the discrete analogue of the continuous derivative formula
The more familiar form of this recurrence,
may be interpreted combinatorially: a $k$-element subset $K$ of $X + 1$ is either entirely contained in $X$, or is determined by the $(k-1)$-element subset of $X$ that is $K \cap X$.
See also
Last revised on October 15, 2018 at 17:15:35. See the history of this page for a list of all contributions to it.