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.

  • $\begingroup$ 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? $\endgroup$ – Ofir Jun 23 '12 at 22:32
  • 1
    $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan Jun 24 '12 at 1:04
  • $\begingroup$ How can we find Fix(g)? Thank you $\endgroup$ – bluemuse Mar 23 '18 at 0:12
  • $\begingroup$ @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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.