Stirling Numbers of the First Kind - a direct derivation

Usually, the Stirling numbers of the first kind are defined as the coefficients of the rising factorial: $(*) \prod_{i=0}^{n-1}(x+i) = \sum_{i=0}^{n} S(n,i) x^i$.

With this definition, a recursive relation of $S(n,i)$ be derived, and it can be shown that is coincides with the recursive relation on the number of permutation on an n-set with i cycles and they have the same initial conditions, hence they coincide.

1) Is there any possibility to do it the other way around, i.e., define $S(n,i)$ combinatorially and then to show that $\prod_{i=0}^{n-1}(x+i) = \sum_{i=0}^{n} S(n,i) x^i$ holds for $x \in \mathbb{N}$ by some combinatorial argument, and thus it is a polynomial identity?

(For Stirling numbers of the second kind, it is possible: it can be shown that $n^k = \sum_{i=0}^{k} \binom{n}{i} i! S_2(k,i)$ combinatorially ($n^k$ counts function from $[k]$ to $[n]$).)

2) Additionally: equating coefficients in $(*)$ shows that $S(n,i)$ is the elementary symmetric polynomial on $n$ variables of degree $n-i$ evaluated on $(0,1,\cdots ,n-1)$. Is there a combinatorial interpretation of this?

Solution 1:

Yes. We'll count the number of multisets of size $k$ on a set of $n$ elements in two ways. First, the usual stars-and-bars argument shows that this is equal to $${n+k-1 \choose k} = \frac{n(n+1)...(n+k-1)}{k!}.$$

Second, the symmetric group $S_k$ acts on the set of functions $[k] \to [n]$ (where $[n] = \{ 1, 2, ... n \}$) and its orbits can be identified with multisets of size $k$. By Burnside's lemma the number of orbits is therefore $$\frac{1}{k!} \sum_{\pi \in S_k} \text{Fix}(\pi).$$

Now verify that if $\pi$ is a permutation with $c$ cycles then it fixes $n^c$ functions. The conclusion follows.

Solution 2:

I don't know whats going on but the question's title is provoking laymen. Stirling numbers(1st kind)

$ 1, 1+1/2, 1+1/2+1/3, 1+1/2+1/3+1/4, ..... $ after computing lcm gives Stirlings in the numerators and factorial in the denominators.