# Generating functions for Stirling numbers

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.

• 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, 2012 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, 2012 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, 2012 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, 2012 at 14:07

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.

• ok, finally understood.. nice proof, thank you very much :-)
– xan
Mar 18, 2012 at 18:06