Tuesday, August 6, 2013

Generalizing binomial coefficient to negative integers

Generatingfunctionology claims that $ \binom{n}{k} = 0$  for $k < 0$. I have checked using formula $ \binom{n}{k} = {n! \over k! (n-k)!}$ and the fact that$$0! = 1 = (-1)! * 0\ \ \text{ identical to }\ \ (-1)! = {1 \over 0}$$$$-1! = (-2)! * (-1)\ \ \text{ identical to }\ \ (-2)! = {1 \over 0 (-1)}$$$$-2! = (-3)! * (-2)\ \ \text{ identical to }\ \ (-3)! = {1 \over 0 (-1)(-2)}$$and, generally,$$(-n)! = {1 \over 0 (-1)(-2) \cdots (-n+1)}$$

I have got the following Karnaugh map, which shows whether $ \binom{n}{k} = 0$ or not,

n > 0
= =
n>k = =
k > 0

You see a checkerboard order of =0 and ≠0: every time we switch one of the conditions, n>k, n>0 or k>0, the output $ \binom{n}{k}$ switches between zero to non-zero. The same checkerboard behaviour is also observed in Wikipedia. Now, we see that author's statement that "$ \binom{n}{k} = 0$ vanishes unless 0 ≤ k ≤ n" is true only for $n > 0$.

No comments: