Is $n \choose k$ defined when $k < 0$? What about $n < k$?

Question

I know that ${n \choose 0} = 1$, and this makes sense to me based on my understanding of combinatorics.

But what about ${n \choose -1}$? My instinct is that this is undefined, since it is equivalent to $\frac{n!}{k!(n - k)!}$, which when $k = -1$ equals $\frac{n!}{(-1)!(n + 1)!}$, and factorials are only defined for non-negative integers.

Similarly, ${5 \choose 6} = \frac{5!}{6!(5 - 6)!} = \frac{5!}{6!(-1)!}$ should also be undefined. However, intuitively it seems to me that "5 choose 6" could also equal $0$, since there are no combinations of 6 objects to be made from a set of only 5 objects.

So, is $n \choose k$ defined when $k < 0$? What about $n < k$? And in either case, what's the reasoning?

Answer 1

It is customary to define $\binom{n}k=0$ for $0\le n<k$. If you restrict $n$ and $k$ to the non-negative integers and think of $\binom{n}k$ as the number of $k$-element subsets of an $n$-element set, then $\binom{n}k$ should certainly be $0$ when $n<k$. If instead you use the more general algebraic definition of the binomial coefficient,

$$\binom{x}k=\frac{x^{\underline k}}{k!}=\frac{x(x-1)(x-2)\ldots(x-k+1)}{k!}$$

for real $x$ and non-negative integer $k$, you automatically get $\binom{n}k=0$ when $n$ is a non-negative integer less than $k$. (Here $x^{\underline k}$ is a falling factorial.)

Not everyone defines $\binom{n}k$ for negative integers $k$, but when it is defined for them, it’s defined to be $0$. This ensures that the Pascal triangle identity,

$$\binom{n}k=\binom{n-1}{k-1}+\binom{n-1}k\;,$$

holds even for $k=0$ (and for integers $k<0$ as well, of course); this is convenient in some induction proofs, for instance.

Answer 2

You can define all the different cases, once you extend factorial to all real numbers using the $\Gamma$ function. Some values may not be defined since the $\Gamma$ function at non-positive integers blows up to infinity.

Answer 3

As one of the other users suggested, you can indeed extend $\binom{n}{k}$ to cases where $k<0$ using the Gamma function. However, there are more ways to do it. For example, if we want to have $n$ be negative. Let $r=|n|$ and $f=r+k-1$, then

\begin{align}\binom{-r}{k} &= \frac{-r\cdot-(r+1)\dots-(r+k-2)\cdot-(r+k-1)}{1\cdot2\cdot3\cdot4\cdot5\cdots k}\\ &=(-1)^k\;\frac{r\cdot(r+1)\cdot(r+2)\cdots(f-2)\cdot(f-1)\cdot f}{1\cdot2\cdot3\cdot4\cdot5\cdots k}\\ &=(-1)^k\binom{f}{k}\\ &=(-1)^k\left(\!\!\binom{f-k+1}{k}\!\!\right)\\ &=(-1)^k\left(\!\!\binom{r}{k}\!\!\right)\;,\end{align} where $\left(\!\!\binom{r}{k}\!\!\right)=\frac{r^{(k)}}{k!}=\frac{r\cdot(r+1)\cdot(r+2)\cdots(r+k-1)}{1\cdot2\cdot3\cdot4\cdot5\cdots k}$. These types of things arise naturally in the study of multisets. In fact, one uses these often in Mathematical Biology while studying genetics. However, this is beyond "normal" probability/combinatorics. The reason it is often the case that $0\leq k$ and $0 \leq n$ is $k$ and $n$ often represent a number of objects, which must be nonnegative. The reason that $k\leq n$ is just as you suggest, one would obtain negative factorials (which require the Gamma function). Moreover, in the case where $2=n<k=3$, how does one take 3 total objects from a possible 2? It can't be done nor does it make sense. So it is natural to only consider $k\leq n$.

Answer 4

You can use the gamma function to extrapolate the factorial function to all real (or complex) numbers except negative integers, but this involves analysis and is kind of arbitrary. The binomial coefficient $\binom x k$ is naturally defined for all integers $k\ge0$ and all real or complex numbers $x$, as it is simply a polynomial function of $x$, namely $x(x-1)(x-2)\cdots(x-k+1)/k!$. Of course the value is $0$ for $x=0,1,\dots,k-1$.