[Math] Generating functions for Stirling numbers

generating-functionsstirling-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.

Best Answer

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.