I came across the following proofwiki page: https://proofwiki.org/wiki/Definition:Stirling_Numbers_of_the_First_Kind/Signed
In definition 2, author states that:
Signed Stirling numbers of the first kind are defined as the polynomial coefficients $s(n,k)$ which satisfy the equation $x^\underline{n} = \sum_k{s(n,k)x^k}$ where $x^\underline{n}$ denotes the nth falling factorial of x.
Why? How was this polynomial expression derived? It just states a definition, and provides no proof.
Is there a proof for this?
If you know the combinatorial definition of $s(n,k)=(-1)^{n-k}c(n,k)$, where $c(n,k)=$ # {permutations in $S_n$ with k cycles}. Then the equation $x(x-1) \dots (x-n+1) = \sum_k s(n,k) x^k$ equivalent to $$x(x+1)\dots (x+n-1) = \sum_k c(n,k)x^k.$$ Now this equation has a combinatorial interpretation, both sides are counting the following objects: $$\#\{(\pi,f):\pi \in S_n, f:\{\text{cycles of } \pi\} \to [x]\}, \text{ where } [x]:=\{1,2,\dots,x\}.$$
RHS should be pretty clear. To see that the LHS is counting the above objects, you can think with the following steps:
Put the first 1, and choose one number from [x] -- $x$ choices
For 2, you have two choices: one is to start a new cycle, and choose one number from [x]; or join the cycle with 1 -- $x+1$ choices
repeat, until you have put all n numbers into a cycle...