1
$\begingroup$

I just started studying higher combinatorics, but until now in the combinatorial sense I had only seen binomial theorem and coefficients. Therefore, I'm having a lot of difficulty in grasping the materials. I recently studies Stirling numbers of the first kind and second kind, though I mostly concentrated on the second kind, and I learned that something like $S_{n,k}$ let's us partition $n$ elements into exactly $k$-partitions. For example, if $n=4$, and $k=2$, then we can partition the $4$ element set into two partitions, either making one partition contain $1$ element and the other $3$ element, or making both of the partitions contain $2$ elements, where I also saw that $S{n,2} = 2^{n-1}-1$.

Anyway, now I entered into the realm of generating functions, and I don't exactly understand what are they, why we need them, and particularly what are their relation with Stirling numbers that I studied lately? I know that this seems like a broad question, but I would like to hear something about this connection. I have already been reading book, and checking Wikipedia, but it is still not clear to me.

$\endgroup$
1
$\begingroup$

Generating functions are functions for whom the coefficients of the taylor series expansions match up with some discrete combinatorics problem. They are useful in the field of Analytic Combinatorics, where one uses complex analysis to generate asymptotic approximations for large values...for instance, it can be hard to compute a combinatorics problem when we start counting in the thousands or tens of thousands objects, but with the generating function and some complex analysis, we can get a very good, close estimate of the answer.

Also, with the right symbolic manipulations, we can FIND the generating functions for new counting problems, a good book on this is Analytic Combinatorics, by Flajolet and Sedgewick.

$\endgroup$
1
  • $\begingroup$ And how do they relate with Stirling numbers? $\endgroup$ – user72151 Nov 16 '15 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy