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.

I've got problems with understanding generating functions, it's completely new topic for me. Some of them are easy, but some sequences like Stirling numbers of the first kind are difficult and so them generating functions too.

For example I'm wondering how can I deduce exponential generating function for Stirling numbers of the first kind. Wikipedia says:

$\sum_{k=0}^{+\infty}u^k\sum_{n=k}^{+\infty} \left[\begin{array}{c}n\\k\end{array}\right] \frac{z^n}{n!}=e^{u\log(1/(1-z))}$

but I never liked to take something as a fact. I understand that probably deducing such a formula isn't a simple thing but how can I do that? I don't know where does it come from. Is there a simple way do prove this equality? I don't like difficult proofs ;-)

Similar questions:

  1. Is there any exponential generating function $A(z)=\sum_{k=0}^{+\infty}\left[\begin{array}{c}n\\k\end{array}\right] \frac{z^k}{k!}$?
  2. Why $\sum_{n=k}^{+\infty} \left[\begin{array}{c}n\\k\end{array}\right]\frac{z^n}{n!}=\frac{\log^k(1/(1-z))}{k!}$ ?

I would be very grateful for patience.

share|improve this question
1  
The double generating function is a consequence of the expression of $\sum\limits_k\left[\begin{array}{c}n\\k\end{array}\right]x^k$ given on the WP page. –  Did Mar 18 '12 at 12:48
    
ok, suppose that I understand this expression, but how double generating function is a consequence of it? can you make it clear for me? –  xan Mar 18 '12 at 13:10
    
I could do so but here is a problem: I still have no clue whatsoever about what you know, what you tried, where is your problem with the explanations on the WP page, what you understood from the answers to the quite similar recent questions you asked on the site, and so on. You see, all this does not help me much to concoct an adapted answer... –  Did Mar 18 '12 at 13:47
    
I don't know much.. I know and understand basics like recurrence for Stirling numbers, basic generating functions like for $H_n$ also $x^{\overline{n}}= \sum_{k} \left[\begin{array}{c}n\\k\end{array}\right]x^k $ is quite understandable for me.. But how to get from this, for example generating function for $\sum_{k=0}^{+\infty}\left[\begin{array}{c}n\\k\end{array}\right] \frac{z^k}{k!}$ or $\sum_{n=k}^{+\infty} \left[\begin{array}{c}n\\k\end{array}\right]\frac{z^n}{n!}$ ? No idea, I'm not good in arithmetics. –  xan Mar 18 '12 at 14:07

1 Answer 1

up vote 3 down vote accepted

The most conceptual explanation uses composition of species.

Recall that your Stirling number of the first kind counts collections of $k$ cycles that together contain $n$ points.

Now, you first determine the exponential generating function for cycles:

There are $(n-1)!$ cycles of length $n$, for example, because you regard the list of elements coming after 1 in the cycle.

So, you get $Cycles(z)=\sum_n \frac{(n-1)!}{n!}z^n= \sum \frac{z^n}{n}= \log(\frac 1 {1-z})$.

Then, you determine the exponential generating function for sets of size $k$.

There is only one possibility to do so and it has size $k$:

$Sets_k(z)=\frac{z^k}{k!}$

And, now the miracle occurs:

You want to count $k$-sets of cycles and you find the exponential generating function by calculating $Sets_k$ of $Cycles$ with composition of functions.

So, you get $Sets_k(Cycles(z))= \frac{(\log(\frac 1 {1-z}))^k}{k!}$.

You can read more on this on the corresponding Wikipedia page or you can read much more on this in the book Combinatorial Species and Tree-Like Structures by F. Bergeron, Gilbert Labelle, Pierre LeRoux.

share|improve this answer
    
ok, finally understood.. nice proof, thank you very much :-) –  xan Mar 18 '12 at 18:06

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.