Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
(So far mine is the only one of four answers to give the combinatorial interpretation. But further edits seem to be happening fast. . . . .) –  Michael Hardy Oct 20 '12 at 21:57
add comment

5 Answers 5

up vote 7 down vote accepted

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

share|improve this answer
    
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|$. –  robjohn Oct 20 '12 at 22:49
    
This is the kind of thing I was looking for when I asked for a combinatorial interpretation. Thanks. –  Snowball Oct 22 '12 at 21:21
add comment

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

share|improve this answer
    
I'd have said "$k$ factors" instead of "$k$ terms", on the theory that "terms" are things that get added or subtracted. –  Michael Hardy Oct 20 '12 at 22:24
    
@MichaelHardy: so changed since it is more precise. However, I often call the summands in a sum, and the factors in a product, terms. –  robjohn Oct 20 '12 at 22:31
    
@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}$? –  NaN Dec 8 '13 at 15:32
1  
@FoF: actually, the Generalized 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$. –  robjohn Dec 8 '13 at 18:18
add comment

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.

share|improve this answer
    
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.) –  Harald Hanche-Olsen Oct 20 '12 at 21:52
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. –  Snowball Oct 20 '12 at 21:55
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. –  Brian M. Scott Oct 20 '12 at 21:57
    
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}$. –  Harald Hanche-Olsen Oct 20 '12 at 21:59
    
@Harald: Someone used exactly that in a question here a few days ago. –  Brian M. Scott Oct 20 '12 at 22:00
add comment

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

share|improve this answer
    
For a combinatorial interpretation, one should first answer the question, what is the combinatorial interpretation for $(-n)!$? –  user17762 Oct 20 '12 at 21:52
    
For a negative integer $x$, $\Gamma(x+1)$ is undefined (or $\infty$). Limiting to $x$ can fix this. –  robjohn Oct 20 '12 at 22:04
    
@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. –  user17762 Oct 20 '12 at 22:07
    
Which is what I meant by "limiting to $x$". :-) –  robjohn Oct 20 '12 at 22:34
    
@robjohn Oh ok. I didn't get it the first time. :-) –  user17762 Oct 20 '12 at 22:39
show 2 more comments

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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