10
$\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

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
    By including $x-1$ boundary markers with $k$ identical elements, I usually think of the number of multisets of size $k$ in a set of size $x$ as $\binom{x+k-1}{k}$, which does happen to equal $\left|\binom{-x}{k}\right|$. However, I don't think I've ever gone from that interpretation to $\left|\binom{-x}{k}\right|$.2012-10-20
  • 0
    This is the kind of thing I was looking for when I asked for a combinatorial interpretation. Thanks.2012-10-22
7

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

  • 0
    I'd have said "$k$ factors" instead of "$k$ terms", on the theory that "terms" are things that get added or subtracted.2012-10-20
  • 0
    @MichaelHardy: so changed since it is more precise. However, I often call the summands in a sum, and the factors in a product, [terms](http://en.wikipedia.org/wiki/Term_%28mathematics%29).2012-10-20
  • 0
    @robjohn, that observation about the negative exponent, where you applied that binomial theorem at $(1+x)^{-n}$ was a new insight for me. One question I have is, why on the RHS can we replace the $-n$ that ordinarily appears in the $\sum_{k=0}^{-n}$ of the Binomial Theorem with $\sum_{k=0}^{\infty}$?2013-12-08
  • 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
7

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
    How common is the notation $x^{\underline k}$? I like it, but can't recall seeing it a lot in the wild. And is there a corresponding $x^{\bar k}$, perhaps meaning $x(x+1)\cdots(x+k-1)$? (Ah, I see you added a reference while I wrote this comment. The Pockhammer symbol. It rubs me the wrong way.)2012-10-20
  • 1
    @HaraldHanche-Olsen: I think the notation originates from the book *Concrete Mathematics* by Graham, Knuth, and Patashnik, so it's relatively new. It's also used in *Combinatorics and Graph Theory* by Harris, Hirst, and Mossinghoff.2012-10-20
  • 1
    @Harald: Yes, it’s paired with that notation for the rising $k$-th power. I picked it up from Graham, Knuth, & Patashnik, *Concrete Mathematics*; I’ve seen it elsewhere, but not as often as I’d like.2012-10-20
  • 0
    Ah, thanks. It seems one should avoid it with exponents having descenders. $x^{\underline j}$ doesn't look so good. If I were to invent my own, I'd probably go for something like $x^{j\downarrow}$.2012-10-20
  • 0
    @Harald: Someone used exactly that in a question here a few days ago.2012-10-20
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
    For a combinatorial interpretation, one should first answer the question, what is the combinatorial interpretation for $(-n)!$?2012-10-20
  • 0
    For a negative integer $x$, $\Gamma(x+1)$ is undefined (or $\infty$). Limiting to $x$ can fix this.2012-10-20
  • 0
    @robjohn for negative integer $x$ and positive integer $y$, we can define it as the limit since $\displaystyle \lim_{x_0 \to x} \dfrac{\Gamma(x_0+1)}{\Gamma(x_0-y+1)}$ exists.2012-10-20
  • 0
    Which is what I meant by "limiting to $x$". :-)2012-10-20
  • 0
    @robjohn Oh ok. I didn't get it the first time. :-)2012-10-20
  • 0
    In my opinion this is a very bad way to approach negative-upper-index binomial coefficients, unless you must absolutely consider the case with non-integer lower index, which in my experience is almost never (but YMMV). Being able to view the most commonly used (integer) cases only as limits of non-integer cases that have no obvious interpretation is just dreadful for intuition (to me). Also the formula used seems to force you to preserve symmetry $\binom nk=\binom n{n-k}$ when $n<0$, but this is **bad**: if $\binom{-1}{-1}=\binom{-1}{0}=1$ then Pascal's recurrence fails at $(n,k)=(0,0)$.2013-12-07
  • 0
    @MarcvanLeeuwen Ok. Your opinion.2013-12-07
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.