3 ms·
Generating functions and counting
- dododo 16y agoi 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 :-)
- carterschonwald 16y agofor 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
- jimmyjim 16y agoI would love to get a hold of that book, but it seems to be unavailable from your link. I cannot find it anywhere else, would you happen to have another link? If you have it yourself, could you please upload it?
- vsingh 16y agoThis appears to be the book, on Scribd: http://www.scribd.com/doc/7846856/Generatingfunctionology-H-Wilf http://www.scribd.com/doc/7846856/Generatingfunctionology-H-...
- TY 16y agoHere is the direct link to the PDF version of the second edition published in 1994 (third one published in 2006 is in print though): http://www.math.upenn.edu/~wilf/gfology2.pdf http://www.math.upenn.edu/~wilf/gfology2.pdf