Generating functions and counting

i read some of this book (analytic combinatorics). it's quite nice in that if you can write down something akin to a grammar that constructs objects you want to count, it provides a set of rewrite rules to actually count them. unfortunately it doesn't provide a way to count anything more complex recursively than a tree that i could see.

for understanding the tree results, the key thing to understand appears to be lagrange's inversion theorem: http://en.wikipedia.org/wiki/Lagrange_inversion_theorem (i think it's also in an appendix in the book)

an interesting connection between probability/ai and this: the probability generating function is a normalized form of these generating functions that allows you to specify a probability distribution: http://en.wikipedia.org/wiki/Probability_generating_function

in particular, you can use this to work out the average size of a tree picked at random :-)

for those who'd like to learn more about generating functions, one of the best books on such, generatingfunctionology by wilf, is available as a free pdf online at www.math.upenn.edu/~wilf/DownldGF.html