11
$\begingroup$

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.

  • 0
    (So far mine is the only one of four answers to give the combinatorial interpretation. But further edits seem to be happening fast. . . . .)2012-10-20

5 Answers 5

2

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.

8

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

  • 1
    @FoF: actually, the [Generalized Binomial Theorem](http://en.wikipedia.org/wiki/Binomial_theorem#Newton.27s_generalised_binomial_theorem) says $ (1+x)^n=\sum_{k=0}^\infty\binom{n}{k}x^k $ The standard Binomial Theorem follows since $\binom{n}{k}=0$ when $n$ is a non-negative integer and $k\gt n$.2013-12-08
8

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.

  • 0
    @Harald: Someone used exactly that in a question here a few days ago.2012-10-20
8

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

  • 0
    This is the kind of thing I was looking for when I asked for a combinatorial interpretation. Thanks.2012-10-22
2

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)}$

  • 0
    @MarcvanLeeuwen Ok. Your opinion.2013-12-07