Generating functions and counting

by guffshemr • 16 years ago

16 5 16 years ago

dododo• 16 years ago

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

carterschonwald• 16 years ago

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

jimmyjim• 16 years ago

I 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• 16 years ago

This appears to be the book, on Scribd: http://www.scribd.com/doc/7846856/Generatingfunctionology-H-...

TY• 16 years ago

Here 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

Generating functions and counting

Related Stories