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?

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.

• Beautiful, thank you. I also think you meant that the functions are from $[k]$ to $[n]$. May I ask where did you encounter this argument? – Ofir Jun 23 '12 at 22:32
• Yes, you're right. I stumbled upon this argument after writing a series of blog posts on the Polya enumeration theorem (starting at qchu.wordpress.com/2009/06/13/…). This is one application of what I call "baby Polya" in that series. – Qiaochu Yuan Jun 24 '12 at 1:04
• How can we find Fix(g)? Thank you – bluemuse Mar 23 '18 at 0:12
• @bluemuse Say $k = 8$ and $\pi = (123)(4567)(8)$. Then $\pi$ fixes every function of the form $f(1) = f(2) = f(3) = \alpha, f(4) = f(5) = f(6) = f(7) = \beta, f(8) = \gamma$ and $\alpha,\beta,\gamma$ can be any of the $n$ colours. Thus there are $n^3$ fixed points. – Trevor Gunn Mar 23 '18 at 0:26

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.