On "theoretical computer science cheat sheet" I found a special formula which is: $$ {n \choose k} = (-1)^k {k-n-1 \choose k}$$
But when I try to expand the value of ${k-n-1 \choose k}$ I have $${k-n-1 \choose k} = \frac{(k-n-1)!}{k!(k-n-1-k)!} = \frac{(k-n-1)!}{k!(-n-1)!}$$ And I am very confused with the factor $(-n-1)!$, because I can count factorial only for positive values, and value $-n-1$ is negative. Can someone explain where I am making a mistake in my thinking?
I think what you are missing is that there is a way to express binomial coefficients without factorials, and this expression works even when some of the terms are negative. Thus: $${n\choose r}={n(n-1)(n-2)\times\cdots\times(n-r+1)\over r!}$$ This formula agrees with the usual one when $n\ge0$, and works even when $n\lt0$, without asking you to compute any factorials of negative numbers. And this formula is what is behind the one on the "cheat sheet".