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

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 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 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 :-)