Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 12 down vote accepted

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.

share|improve this answer
    
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
1  
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

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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