Generating functions for Stirling numbers

Question

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.

Answer 1

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.

Answer 2

Here is an alternative for the double generating function, which was hinted at in the comments.

One of the "signature" properties of the stirling numbers of the first kind is $$ x^{\overline{n}} = \sum_{k=0}^n \left[{n \atop k}\right] x^k $$ where $x$ is an element of any ring, and $x^{\overline{n}} = x(x+1)(x+2)\cdots(x+n-1)$ is the rising factorial.

This leads to $$\sum_{n=0}^\infty \sum_{k=0}^\infty \left[{n\atop k}\right] X^k \frac{Y^n}{n!} = \sum_{n=0}^\infty \Big(\sum_{k=0}^n \left[{n\atop k}\right] X^k\Big) \frac{Y^n}{n!} = \sum_{n=0}^\infty X^{\overline{n}} \frac{Y^n}{n!} = \sum_{n=0}^\infty (-1)^n \frac{(-X)^{\underline{n}}}{n!} Y^n = \sum_{n=0}^\infty \binom{-X}{n} (-Y)^n = (1-Y)^{-X} $$ where in the last step the binomial series was used.

Remark By $$ (1-Y)^{-X} = \exp((-X)\log(1-Y)) = \exp(X\log(1/(1-Y))) $$ this expression is the same as the one stated in the question. But in my optinion the representation $$ (1-Y)^{-X} $$ is more elegant.

Answer 3

$\left[{n\atop k}\right]:$ # permutations of $n$ objects wich involve $k$ cycles. For such a permutation we partition $n$ objects into $k$ cycles: $m_1+m_2+...+m_k=n$ where $m_1,m_2,...,m_k>0.$ There are $n!$ permutations. Cycles can be be permuted in $k!$ ways. Each cycle $m_j$ remains same in $m_j$ ways cyclicly. Therefore, counting gives $$\left[{n\atop k}\right]= \sum_{m_1+m_2+...+m_k=n\\m_1,m_2,...,m_k>0}\frac{n!}{k! m_1m_2...m_k} $$ Needs better explanation. The generating function is then $$ \sum_{n=k}^\infty \left[{n \atop k}\right] \frac{z^n}{n!}\\\small= \sum_{n=k}^\infty\left( \sum_{m_1+m_2+...+m_k=n\\m_1,m_2,...,m_k>0}\frac{n!}{k! m_1m_2...m_k}\right) \frac{z^n}{n!}\\\small=\frac1{k!} \sum_{n=k}^\infty \left(\sum_{m_1+m_2+...+m_k=n\\m_1,m_2,...,m_k>0}\frac{1}{ m_1m_2...m_k}\right)z^n\\ =\frac1{k!}\left(\sum_{m=1}^\infty\frac{z^m}m\right)^k=\frac{(-\ln(1-z))^k}{k!}$$