Why are Stirling numbers of the first kind related to the number of permutations with $k$ cycles?

As discussed e.g. in this other question, as well as the relevant Wikipedia page, we have $$(x)_n \equiv x(x-1)\cdots (x-(n-1)) = \sum_{k=0}^n s(n,k) x^k,$$ where $s(n,k)$ are the so-called Stirling numbers of the first kind. These are also written as $$s(n,k) = (-1)^{n-k} \left[\begin{matrix}n\\k \end{matrix}\right],$$ where $\left[\begin{smallmatrix}n\\k \end{smallmatrix}\right]$ are the unsigned Stirling numbers of the first kind, which are also the coefficients of the polynomial expansion of $x^{\overline n}\equiv x(x+1)\cdots (x+(n-1))$.

It is not hard to see that these are tightly related to sums of powers of integers: $$x^{\bar n} = x^n + x^{n-1}\left(\sum_{k=1}^n(k-1)\right) + x^{n-2}\left(\sum_{i<j=1}^{n}(i-1)(j-1)\right)+\cdots + x\left(\prod_{k=1}^{n}(k-1)\right).$$

The unsigned Stirling numbers $\left[\begin{smallmatrix}n\\k \end{smallmatrix}\right]$ are also equal to the number of permutations of $n$ elements which are composed of exactly $k$ disjoint cycles. E.g. $\left[\begin{smallmatrix}3\\2 \end{smallmatrix}\right]=3$ because the permutations in $S_3$ with two cycles are (in cycle notation), $(12)$, $(13)$, and $(23)$.

Is there a good way to see the connection between these two definitions? More specifically, why are the coefficients of $x^{\overline n}$ connected to the number of this particular type of permutations? Equivalently, why does counting these classes of permutations result in expressions involving these sums of products of integers?

There is a nice proof, which is similar to the proof that $$ (x+1)^n=\sum_{k=0}^n\binom{n}kx^k $$ by counting the number of ways to expand $(x+1)^n$ with the distributive property.

It is helpful to write $x^{\overline n}$ as $$ (x+1+\dots+1)\cdots (x+1+1)(x+1)x $$ When you expand this out with the distributive property, there are $n!$ terms, as you have $n$ choices for the term from $(x+1+\dots+1)$, then $n-1$ choices from the second factor, and so on down to $1$ choice from the $x$ factor. When choosing from the $k^{th}$ factor, there are $n-k+1$ choices, and exactly one choice will increase the resulting power of $x$.

On the other hand, consider the following method of choosing a permutation, $\pi$. You first choose $\pi(1)$, from one of $n$ options. Then, you choose $\pi(\pi(1))$, then $\pi(\pi(\pi(1)))$, and so on until you complete a cycle. Then, you choose $\pi(s)$, where $s$ is the smallest unassigned element, etc. During the $k^{th}$ stage of this process, you have $n-k+1$ options. Exactly one of these leads to the creation of a cycle.

After some thought, these processes are exactly the same, so that the number of ways to choose a permutation with $k$ cycles is the coefficient of $x^k$ in the expansion of $x^{\overline n}$.

The easiest way, probably, is by recursion. Notice that $x^{\overline{n+1}}=(x+n)x^{\overline{n}}$ just by distributing the product, this creates the recursion $${n+1 \brack k}={n \brack k-1}+n\cdot {n \brack k}.$$ The first terms you can think about it by placing $n+1$ as a fix point(so you create a new cycle) and the other term can be seen as placing $n+1$ as the pre-image of some element $x$ and the old pre-image as the preimage of $n+1.$ These choice of $x$ can be done in $n$ ways.

$\require{cancel}$

This answer contains exactly the same information as that of Mike's. It is just more elaborate.

Write the product $x^{\overline{n}}$

$$x^{\overline{n}}=\left(x+\underset{n-1\text{ times}}{\underbrace{1+\dots+1}}\right)\cdots\left(1+x\right)x.$$

Imagine the process of expanding this product from the left. We record which summand (from the left) we choose on the $k$th term $\left(x+\underset{n-k\text{ times}}{\underbrace{1+\dots+1}}\right)$. Say that you chose the $i_k$th summand from the $k$th term. We define a sequence $j_1,\dots,j_n$ by

$$j_{k+1}=i_{k+1}\text{th smallest element in }\{1,\dots,n\}\setminus\{j_1,\dots,j_{k}\}.$$

The sequence $j_1\dots j_{n}$ is a reordering of $1,\dots ,n$. Now for each $k$ such that $i_k=1,$ put a slash "/" between $j_{k}$ and $j_{k+1}.$ This means that if you chose $i$ $x$'s, then you have $i$ slashes. The resulting sequence looks like

$$j_1\dots j_{k_{1}}/j_{k_1+1}\dots j_{k_2}/\dots/j_{k_{i}+1}\dots j_{n},$$

and we can regard this sequence as a permutation which is the product of $i$ cycles. Since every such permutation arises uniquely in this way, the coefficient of $x^i$ in $x^{\overline{n}}$ counts the number of permutations which is the product of precisely $i$ cycles.

As an example, consider the case $n=4$ and $i_1=3$, $i_2=1$, $i_3=2$, and $i_4=1$. In this case $$ \begin{align} j_1&= 3\text{rd smallest element in} \{1,2,3,4\}=3,\\ j_2&= 1\text{st smallest element in} \{1,2,\cancel{3},4\}=1,\\ j_3&= 2\text{nd smallest element in } \{\cancel{1},2,\cancel{3},4\}=4,\\ j_4&= 1\text{st smallest element in} \{\cancel{1},2, \cancel{3},\cancel{4}\}=2,\\ \end{align} $$ so the resulting permutation will be $(31)(42)$.