I am struggling to understand something from my lecture notes. I will state some definitions and then post the excerpt that I can't make sense of.
Definitions:
Let $c(k, n)$ be the number of permutations of $\{ 1, \dots, k \}$ with exactly $n$ cycles. Let $c(0, 0) = 1$.
Let $s(k, n)$ be the Stirling numbers of the first kind.
Excerpt:
Discussion:
I think the proof that the $c(k, n)$ are the coefficients of the expansion of the rising factorial is fairly straightforward. Since $s(k, n)$ are the coefficients of the falling factorial, I think this implies that $c(k, n) = \lvert s(k, n) \rvert$ because the expansion of $x^{(k)}$ should be the same as $(x)_k$ except that all the minus signs become plus signs.
I don't understand the part about $c(k, n) = (-1)^{k + n} s(k, n)$. In the proof, I don't understand what kind of operation "replace $x$ with $-x$" is. I can reason something like the following:
\begin{align*} \sum_{n = 0}^k c(k, n) x^n &= x(x + 1) \cdots (x + k - 1)\\ &= (-1)^k (-x)(-x - 1) \cdots (-x - k + 1) \text{ (pull } -1 \text{ from each of the } k \text{ terms)}\\ &= (-1)^k (-x)_k \text{ (recognizing the falling factorial with } -x)\\ &= (-1)^k \sum_{n = 0}^k s(k, n) (-x)^n\\ &= \sum_{n = 0}^k (-1)^{k + n} s(k, n) x^n, \end{align*}
which concludes the proof. Is that right?
I'm a bit concerned there is an error somewhere because if you look at Wikipedia you see the following:
,
and I don't understand how to reconcile the presence of the minus sign in Wikipedia's version.
I appreciate any help.
‘Replace $x$ by $-x$’ just means substitute $-x$ for $x$ in the equation
$$\sum_{n=0}^kc(k,n)x^n=x^{(k)}\,.$$
When you do that, you get
$$\begin{align*} \sum_{n=0}^kc(k,n)(-x)^n&=(-x)^{(k)}\\ &=(-x)(-x+1)\ldots(-x+k-1)\\ &=(-1)^kx(x-1)\ldots(x-k+1)\\ &=(-1)^k(x)_n\\ &=(-1)^k\sum_{n=0}^ks(k,n)x^n\\ &=\sum_{n=0}^k(-1)^ks(k,n)x^n\,. \end{align*}$$
and
$$\sum_{n=0}^kc(k,n)(-x)^n=\sum_{n=0}^k(-1)^nc(k,n)x^n\,,$$
so $(-1)^nc(k,n)=(-1)^ks(k,n)$ for $n=0,\ldots,k$, and therefore $c(k,n)=(-1)^{k-n}s(k,n)=(-1)^{n+k}s(k,n)$ for $n=0,\ldots,k$. Your computation also works.
There is no conflict with Wikipedia’s $s(n,k)=(-1)^{n-k}{n\brack k}$:
$$(-1)^{n-k}=(-1)^{k-n}=(-1)^{n+k}\,,$$
since $n-k$, $k-n$ and $n+k$ all have the same parity.