For positive integers $n$ and $k$, what is the meaning of $\binom{-n}{k}$?
Specifically, are there any combinatorial interpretations for it?
Edit: I just came across Daniel Loeb, Sets with a negative number of elements, Advances in Mathematics. 91 (1992), 64-74, which includes a combinatorial interpretation for $\binom{n}{k}$ for any $n,k \in \mathbb{Z}$ in theorem 5.2.
$\endgroup$ 05 Answers
$\begingroup$It is the binomial coefficient for a negative exponent: $$ \begin{align} (1+x)^{-n} &=\sum_{k=0}^\infty\binom{-n}{k}x^k\\ &=\sum_{k=0}^\infty(-1)^k\binom{k+n-1}{k}x^k \end{align} $$ Note that this follows from the following formulation of the standard binomial coefficient: $$ \begin{align} \binom{-n}{k} &=\frac{\overbrace{-n(-n-1)(-n-2)\dots(-n-k+1)}^{k\text{ factors}}}{k!}\\ &=(-1)^k\frac{(n+k-1)(n+k-2)(n+k-3)\dots n}{k!}\\ &=(-1)^k\binom{n+k-1}{k} \end{align} $$
$\endgroup$ 4 $\begingroup$For integers $n,k\ge 0$,
$$\binom{-n}k=\frac{(-n)(-n-1)(-n-2)\dots(-n-k+1)}{k!}\;.$$
Thus, $$\binom{-3}4=\frac{(-3)(-4)(-5)(-6)}{4!}=15\;.$$
In fact $\dbinom{x}k$ is defined for all real $x$ and integers $k\ge 0$ by
$$\binom{x}k=\frac{x^{\underline k}}{k!}\;,$$
where $$x^{\underline k}=x(x-1)(x-2)\dots(x-k+1)$$ is a so-called falling factorial or falling $k$-th power.
$\endgroup$ 5 $\begingroup$If $x$ is any complex number and $k$ is a non-negative integer then one can take $\dbinom x k$ to be $$ \frac{x(x-1)(x-2)\cdots(x-k+1)}{k!} $$ (so that the number of factors in the numerator is $k$, as in the denominator). In particular, $\dbinom x 0=1$.
Combinatorial interpretation:
If $x$ is a positive integer, then $\left|\dbinom {-x}{k}\right|$ is the number of multisets of size $k$ in a set of size $x$.
$\endgroup$ 1 $\begingroup$One way to define $\dbinom{x}{y}, \forall x,y \in \mathbb{C}$ is $$\dbinom{x}{y} = \dfrac{\Gamma(x+1)}{\Gamma(y+1) \Gamma(x-y+1)}$$
$\endgroup$ 7 $\begingroup$For this answer it would probably be best if you're familiar with the Binomial distribution.
I like the interpretation through probability & statistics via the negative binomial distribution. Let's say we're watching a sequence of cointosses (let's call tossing a "heads" a success and "tails" a failure) where the probability of a success is independently $p$. Then the negative binomial distribution is a distribution over the waiting times till the $r$th success. In other words, what's the probability we'll have to wait $t$ tosses/trials to see $r$ successes, $p(t|r,p)$?
Equivalently, by the $t-1$ trial we must have seen $r-1$ successes and $k=t-r+1$ failures. But then $t=k+r-1$, and so there are $\binom{k+r-1}{k}$ ways to observe $k$ failures and $r$ successes in $t$ trials. Since $r$ and $k$ completely specify $t$, we can re-parameterize and write the probability that the $r$th success occurs on the $(r+k)$th trial as
\begin{equation} p(k|r, p) = \binom{k+r-1}{k} p^r (1-p)^k \end{equation}
Why the name negative binomial (and why is this an answer to your question)? Well, because
\begin{equation} \binom{k+r-1}{k} = \frac{(k+r-1)_k}{k!} = \frac{(k+r-1)(k+r-2)\dots(r-1)}{k!} = (-1)^k \frac{(-r+1)\dots(-r -k+1)}{k} = (-1)^k \binom{-r}{k} \end{equation}
Note that for integer $r$ the negative binomial distribution may be called the Pascal distribution.
$\endgroup$ 0
