3
$\begingroup$

This is a question about "nasty details" of the binomial coefficients.

I would like to understand the definition of binomial coefficients $ n \choose k $ for general integers $n$ and $k$.

One way to define binomial coefficients is as the number of cardinality $k$ subsets of an cardinality $n$ subsets, which is,

${n \choose k} := |\{\; S \subseteq \{ 1, \dots, n \} \;:\; |S| = k \;\}|$

This formula is well-defined for any integer $n$ and $k$. Note that for $k = 0$ we always get ${n \choose k} = 1$ regardless of $n$ but generally it is zero for negative $n$.

There are many other ways of defining the binomial coefficients. For instance, another definition is:

${n \choose k} := \prod_{i=1}^k \dfrac{ n+1-i }{ i }$

which is equals $1$ for any non-positive $k$ regardless of $n$. Argueably, the latter definition of the binomial coefficients is not regarded as "foundational" for non-negative $n$ and $k$, but that does not really help in deciding for integers the binomial coefficients are defined and what their values are.

Is there a commonly accepted definition of ${n \choose k}$ for any integers $n$ and $k$, and what are the benefits of that definition for the working mathematician?

$\endgroup$
4
$\begingroup$

My preferred definition is:

$$\binom{x}k=\begin{cases} \frac{x^{\underline{k}}}{k!},&\text{if }0\le k\in\Bbb Z\\ 0,&\text{if }0>k\in\Bbb Z\,, \end{cases}$$

where $x$ can in principle be any complex number (though I’ve only actually seen it used with $x\in\Bbb R$), and $x^{\underline{k}}$ is a falling factorial. This behaves correctly for non-negative integer values of $x$ and $k$, behaves as it ought for negative integer $k$, works well in connection with manipulation of generating functions, and makes the binomial coefficient a polynomial in $x$ of degree $k$, which can be useful.

$\endgroup$
3
$\begingroup$

If you want the binomial coefficients ${s \choose k}$ to satisfy the binomial theorem

$$(1 + x)^s = \sum_{k \ge 0} {s \choose k} x^k$$

in the greatest generality possible, then by repeatedly taking derivatives you can see that you are required to define

$$\boxed{ {s \choose k} = \frac{s(s-1) \dots (s - (k-1))}{k!} }.$$

Here $k$ is still a nonnegative integer but $s$ can be an arbitrary complex number (at least; $s$ can take values in any commutative $\mathbb{Q}$-algebra). This definition together with the binomial theorem shows that, for example, we still have Vandermonde's identity

$${s+t \choose k} = \sum_{i+j=k} {s \choose i} {t \choose j}$$

for arbitrary complex $s, t$, and in fact as a polynomial identity in $s$ and $t$.

Specializing, if $s$ is a negative integer we get the negative binomial coefficients, which are combinatorially meaningful since they describe the Taylor series expansion of

$$\frac{1}{(1 - x)^n} = \sum_{k \ge 0} (-1)^k {-n \choose k} x^k$$

which gives that $(-1)^k {-n \choose k} = {n+k-1 \choose k}$ is the number of solutions to $a_1 + \dots + a_n = k$ for non-negative integers $a_i$; see stars and bars for more on this. See also, for example, the negative binomial distribution.

Even non-integer values of $s$ are combinatorially meaningful; for example $s = -\frac{1}{2}$ shows up in the generating function of the central binomial coefficients. If we consider $s$ to be a formal variable then $\frac{1}{(1 - x)^s}$ can be thought of as a two-variable generating function for the (unsigned) Stirling numbers of the first kind (and we get the signed Stirling numbers of the first kind with $(1 + x)^s$).

Some people might go further and generalize $k$ using the Gamma function but I have personally never needed to do this. I know exactly one place where it shows up, which is the Beta function. My preferred convention is that ${s \choose k}$ is only defined for $k$ a nonnegative integer; that's all I've ever needed.

$\endgroup$
2
  • $\begingroup$ I know at least one reason to define $n \choose k$ for negative $k$: the alternating algebra for $\bigwedge^k \mathbb R^n$ should be zero-dimensional for negative $k$, so that the de Rham complex has trivial infinite extensions in both directions. That motivates setting ${n \choose k} := 0$ for negative $k$ and non-negative $n$. What do you think? $\endgroup$ – shuhalo Sep 15 '20 at 22:06
  • $\begingroup$ @shuhalo: I guess it’s a matter of convention but I would just say that it’s undefined. The exterior power is a certain quotient of the tensor power and the tensor power is undefined for negative exponent unless the input is invertible. $\endgroup$ – Qiaochu Yuan Sep 15 '20 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.