# How to Count.

April 22, 2010 1:00 AM Subscribe

A generating function is a way to keep track of a lot of related numbers all at once... The study of generating functions is an art and a science known as 'generatingfunctionology,' and its bible is free for all to download.

Generating functions are functions which count things. For example, the generating function for the binomial coefficients n-choose-k is (x+1)^n; expanded as a sum, the coefficient of x^k is n-choose-k. But you can find other functions that count the Fibonacci numbers, the Catalan numbers, or any of a thousand other sequences of dreadfully interesting numbers.

Marko Petkovsek, Herbert Wilf and Doron Zeilberger wrote a kind of follow-up to Generatingfunctionology called 'A=B,' which you can also download for free. This incredible book describes how to automate the process of finding recurrence relations (like the Fibonacci relation) on a set of numbers. For people who count combinations of things (combinatorialists, you might call them) this algorithm solves problems by the dozen that previously would have taken years.

Generating functions are functions which count things. For example, the generating function for the binomial coefficients n-choose-k is (x+1)^n; expanded as a sum, the coefficient of x^k is n-choose-k. But you can find other functions that count the Fibonacci numbers, the Catalan numbers, or any of a thousand other sequences of dreadfully interesting numbers.

Marko Petkovsek, Herbert Wilf and Doron Zeilberger wrote a kind of follow-up to Generatingfunctionology called 'A=B,' which you can also download for free. This incredible book describes how to automate the process of finding recurrence relations (like the Fibonacci relation) on a set of numbers. For people who count combinations of things (combinatorialists, you might call them) this algorithm solves problems by the dozen that previously would have taken years.

generating functions are the best thing ever. At least, they're good enough for me to write a PhD thesis that has them on basically every page.

posted by madcaptenor at 4:06 AM on April 22, 2010

posted by madcaptenor at 4:06 AM on April 22, 2010

This was described in a previous post which was described in a previous post.

posted by twoleftfeet at 4:20 AM on April 22, 2010 [2 favorites]

posted by twoleftfeet at 4:20 AM on April 22, 2010 [2 favorites]

Yeah, I do that too........................................................................,...........

— doublehappy

posted by krilli at 4:24 AM on April 22, 2010

This was described in a previous post which was described in a previous post which was described in a previous post.

posted by Joe in Australia at 4:29 AM on April 22, 2010

posted by Joe in Australia at 4:29 AM on April 22, 2010

Combinatorists do it when it counts. Generatingfunctionalogy is the smuttiest compound term I've heard this month.

posted by twoleftfeet at 4:29 AM on April 22, 2010 [2 favorites]

posted by twoleftfeet at 4:29 AM on April 22, 2010 [2 favorites]

If you want a better understanding of mathematical papers and stuff, A lot of people have said good things about Khan Academy which is a bunch of free videos about mathematics and stuff.

posted by delmoi at 4:44 AM on April 22, 2010

posted by delmoi at 4:44 AM on April 22, 2010

Wikipedia's math entries are so worthless. They need to be less technical and more explanatory. The actual linked book is a little more helpful, although I have to express some skepticism about the idea.

As I understand it, I find a function that, when I multiply it out, the coefficients happen to be the numbers I'm looking for. Like, maybe my sequence is 1 2 1, in which case my generating function could be (x+1)

Naively, it's hard to see how that would be useful. But the book addresses that naive belief, so maybe it's cool. In any case, it's a neat idea to try to run with and see if it goes anywhere.

posted by DU at 4:48 AM on April 22, 2010 [1 favorite]

As I understand it, I find a function that, when I multiply it out, the coefficients happen to be the numbers I'm looking for. Like, maybe my sequence is 1 2 1, in which case my generating function could be (x+1)

^{2}, because that's (1)x^{2}+ (2)x + (1). Is that right? (It's got to be harder than that for open-ended sequences like Fib.)Naively, it's hard to see how that would be useful. But the book addresses that naive belief, so maybe it's cool. In any case, it's a neat idea to try to run with and see if it goes anywhere.

posted by DU at 4:48 AM on April 22, 2010 [1 favorite]

Oh I see, for the harder/longer sequences, you can find a formula that determines that coefficient and because that coefficient is also your sequence, the formula determines your sequence. Clev.

posted by DU at 4:51 AM on April 22, 2010

posted by DU at 4:51 AM on April 22, 2010

*This was described in a previous post which was described in a previous post which was described in a previous post.*

So you're saying a generating function will enable us to predict when it will be posted next? Have you notified them in the Free Will thread?

posted by Obscure Reference at 5:11 AM on April 22, 2010

twoleftfeet: I know the author (he's an emeritus professor in my department) and I don't

posted by madcaptenor at 5:15 AM on April 22, 2010

*think*he intended the term "generatingfunctionology" to be smutty.posted by madcaptenor at 5:15 AM on April 22, 2010

Cripes! Not another one! Is it Maths day on Metafilter or wut? :P

posted by Monkeymoo at 5:38 AM on April 22, 2010 [2 favorites]

posted by Monkeymoo at 5:38 AM on April 22, 2010 [2 favorites]

Is today numbers day? (And I don't mean "Kiss your Anesthesiologist" Day-- I'm pretty sure that is next month.)

posted by Secret Life of Gravy at 6:04 AM on April 22, 2010

posted by Secret Life of Gravy at 6:04 AM on April 22, 2010

(Well, I saw the two other posts on numbers, and thought I'd send off two of my favorite books about counting...)

posted by kaibutsu at 6:54 AM on April 22, 2010

posted by kaibutsu at 6:54 AM on April 22, 2010

Very cool. It makes me a bit sad how much math i've forgotten. And yeah, that's an awesome name for a text book.

posted by chunking express at 7:12 AM on April 22, 2010

posted by chunking express at 7:12 AM on April 22, 2010

doublehappy: Unfortunately, advanced mathematics is simply hard :-( and there isn't really a way to make it easy. I have a degree in math and yet I still consider a lot of this stuff hard going.

Take the Jordan Curve Theorem - any simply closed curve divides the plane into two disjoint regions, the "inside" and the "outside", whose common boundary is the curve.

This seemed so obvious that no one even bothered to demonstrate a proof, until there were... problems - like the fact that "it" isn't true in 3 dimensions. I went through the proof in a topology class in university - it took us at least three classes to go through it. I'm sure I couldn't reproduce that proof now (25 years later) without a lot of help (I could do a few others, Gödel's Theorem and the unsolvability of Hilbert's Tenth Problem, I haven't forgotten everything!)

And at least the statement of the theorem is reasonably understandable. Some other theorems would take you quite a lot of work just to vaguely understand what they are claiming.

My classic example is this definition: "A simple group is one with no proper normal subgroups" where group, proper and normal all have specific mathematical definitions with no real correspondance to the real world.

I could explain to you why normal subgroups are important (because they're kernels of group homomorphisms, silly! ;-) - or to be fair, they are in some sense to groups and mappings like prime numbers are to numbers and multiplication...) but if I then started to prove even the simplest results after that you'd probably balk.

It was too dry for me too - I became a software engineer.

posted by lupus_yonderboy at 8:42 AM on April 22, 2010 [1 favorite]

Take the Jordan Curve Theorem - any simply closed curve divides the plane into two disjoint regions, the "inside" and the "outside", whose common boundary is the curve.

This seemed so obvious that no one even bothered to demonstrate a proof, until there were... problems - like the fact that "it" isn't true in 3 dimensions. I went through the proof in a topology class in university - it took us at least three classes to go through it. I'm sure I couldn't reproduce that proof now (25 years later) without a lot of help (I could do a few others, Gödel's Theorem and the unsolvability of Hilbert's Tenth Problem, I haven't forgotten everything!)

And at least the statement of the theorem is reasonably understandable. Some other theorems would take you quite a lot of work just to vaguely understand what they are claiming.

My classic example is this definition: "A simple group is one with no proper normal subgroups" where group, proper and normal all have specific mathematical definitions with no real correspondance to the real world.

I could explain to you why normal subgroups are important (because they're kernels of group homomorphisms, silly! ;-) - or to be fair, they are in some sense to groups and mappings like prime numbers are to numbers and multiplication...) but if I then started to prove even the simplest results after that you'd probably balk.

It was too dry for me too - I became a software engineer.

posted by lupus_yonderboy at 8:42 AM on April 22, 2010 [1 favorite]

*Unfortunately, advanced mathematics is simply hard :-( and there isn't really a way to make it easy. I have a degree in math and yet I still consider a lot of this stuff hard going.*

I think this is unfair to both math and the person you are talking to. Yes, some, even a lot of, advanced math is "hard" but:

1) There's a lot of math that isn't advanced.

2) There's a lot of advanced math that isn't hard.

Even a person with only a HS education can appreciate a wide body of non-everyday math (i.e. more advanced than arithmetic or even geometry and calculus). Furthermore:

3) There are few "brick walls" out there. It's a pretty smooth gradient from the easier parts to the harder parts and you can keep walking until it gets too be too hard (and maybe try again later when your legs are stronger).

You can create the illusion of difficulty and brick walls by teleporting a distant problem to Level 1 by quoting a theorem at them, but the only thing that does is frighten the student with dragons that will be geckos by the time they ever meet them, if ever.

posted by DU at 10:01 AM on April 22, 2010

If I may take a stab at explaining what a 'generating function' is:

You've probably heard of polynomials--if you remember back to 7th grade algebra, a polynomial involves 'x' and powers of 'x' like:

As you can see, you just took the sequence of numbers: 0, 1, 2, 3, 4, 5, 6,... and stuck them in front of the various powers of 'x' in the infinite polynomial.

Now you can use different sequences to form different and more interesting generating functions.

For instance, the sequence of even numbers (starting with 0) makes this generating function:

Why you might want to do this and how it is useful are the subjects of a much longer post . . . or book, I suppose.

Notes for the very curious:

1. To prove that 1x

2. You'll notice that the equality only holds for x between -1 and 1. If x=2, for example, the polynomial is infinite while 1/(1-2) = -1. However, the polynomial equals 1/(1-x) in every case where the polynomial converges to a finite number, and those are the cases we're really interested in studying.

3. The generating functions outlined above are called 'ordinary generating functions'--there are other types, only slightly more complicated.

posted by flug at 10:44 AM on April 22, 2010 [3 favorites]

You've probably heard of polynomials--if you remember back to 7th grade algebra, a polynomial involves 'x' and powers of 'x' like:

2 + 3x + 4xA generating function is a type of infinite polynomial. Instead of just 2 or 3 or four powers of 'x' we have an infinite number, something like:^{2}

0xOK, you just encountered your first generating function and survived.^{0}+ 1x^{1}+ 2x^{2}+ 3x^{3}+ 4x^{4}+ 5x^{5}+ 6x^{6}+ ...

As you can see, you just took the sequence of numbers: 0, 1, 2, 3, 4, 5, 6,... and stuck them in front of the various powers of 'x' in the infinite polynomial.

Now you can use different sequences to form different and more interesting generating functions.

For instance, the sequence of even numbers (starting with 0) makes this generating function:

0xThe sequence of odd numbers (starting with 1) makes this generating function:^{0}+ 2x^{1}+ 4x^{2}+ 6x^{3}+ 8x^{4}+ 10x^{5}+ 12x^{6}+...

1xAnd the sequence 1, 1, 1, 1, 1,... (a very boring sequence, if I may say) makes the also boring but useful generating function:^{0}+ 3x^{1}+ 5x^{2}+ 7x^{3}+ 9x^{4}+ 11x^{5}+ 13x^{6}+...

1xThe reason that last one is useful is you can use various algebra and/or calculus to prove that it is equal to the simple equation^{0}+ 1x^{1}+ 1x^{2}+ 1x^{3}+ 1x^{4}+ 1x^{5}+ 1x^{6}+...

1/(1 - x)All the above is just the starting point--how you make the most simple kinds of generating function and how in the most useful cases you can reduce the infinite polynomial to a simple equation of some sort.

Why you might want to do this and how it is useful are the subjects of a much longer post . . . or book, I suppose.

Notes for the very curious:

1. To prove that 1x

^{0}+ 1x^{1}+ 1x^{2}+ 1x^{3}+ 1x^{4}+ 1x^{5}+ 1x^{6}+... = 1/(1 - x), just multiply both sides by (1-x).2. You'll notice that the equality only holds for x between -1 and 1. If x=2, for example, the polynomial is infinite while 1/(1-2) = -1. However, the polynomial equals 1/(1-x) in every case where the polynomial converges to a finite number, and those are the cases we're really interested in studying.

3. The generating functions outlined above are called 'ordinary generating functions'--there are other types, only slightly more complicated.

posted by flug at 10:44 AM on April 22, 2010 [3 favorites]

Ah, generatingfunctionology. I think it was the first math book that really blew me away. Do you watch martial arts movies? Where there are people who can fly through the air or snatch arrows in flight? Where there are little men like Mr. Miyagi who can break you in half with their pinky just because

I was a TA for a serious theoretical computer scientist (the only things on his desk were a legal pad and a #2 pencil -- a computer scientist!). I was trying to get him to explain how to do one of the homework problems, and he said "Oh, just a simple generating function" and proceeded to diagram a mathematical Kung Fu pinky death-strike on his blackboard. I said "I know, but

posted by madmethods at 12:04 PM on April 22, 2010

*they really know what the **** they are doing*?. Reading generatingfunctionology was the first time that it sunk in that there really are people like that, they're just hiding in mathematics and many other interesting fields. Kung Fu with numbers.I was a TA for a serious theoretical computer scientist (the only things on his desk were a legal pad and a #2 pencil -- a computer scientist!). I was trying to get him to explain how to do one of the homework problems, and he said "Oh, just a simple generating function" and proceeded to diagram a mathematical Kung Fu pinky death-strike on his blackboard. I said "I know, but

*they haven't learned that yet*". He actually had no idea how to solve it without generating functions (why would he?) so his response to that was "well, why not?".posted by madmethods at 12:04 PM on April 22, 2010

I think there's definitely a lot of combinatorics that's accessible without a lot of prior background. Many of the things I do with permutations, for example, I could explain to high school students without a hitch.

Generating functions are a bit tougher: The idea requires being a bit comfortable with dealing with infinite sums (one of the conceptually hardest parts of calculus, I think) just so that you can follow the calculations, and then you deal with formal power series. In one sense, this is easier because you don't have to worry about stupid shit like convergence. On the other hand, it means throwing away all grounding in reality and admit that you're just playing with symbols in a fancy way. And getting really nice real-world-relevant results from the exercise...

That said, I can imagine meeting space aliens who know how to count but only using generating functions, and the process of matching things to their tentacles to 'count' would be a monstrously hard concept, learned only after decades of schooling... It's a whole different starting point to a whole class of problems.

Speaking of such space aliens, I once saw Richard Stanley give a talk in which generating functions were quite prominent. You can think of the Taylor Series of a trigonometric function as a generating function in itself, and certain of these actually count interesting things. So Stanley was curious about how much of trigonometry you could recover using combinatorics - combining and counting whatever objects it was that these trig functions were generating. The answer, apparently, was quite a lot, so long as you didn't mind that all reference to geometry was lost.

Another race of aliens I like to imagine never deals with integers, except for a few crazy specialists, but instead learn about permutations from an early age and use them for all of their basic mathematical understanding of the world. These aliens never got in to mass production, because for them every object is distinct. You don't have six eggs, you have six objects with all of the properties of eggs, arranged in a particular configuration. And when I switch two of the eggs in the carton, the permutation that describes the eggs has changed...

Ok, enough rambling for now...

posted by kaibutsu at 12:51 PM on April 22, 2010 [1 favorite]

Generating functions are a bit tougher: The idea requires being a bit comfortable with dealing with infinite sums (one of the conceptually hardest parts of calculus, I think) just so that you can follow the calculations, and then you deal with formal power series. In one sense, this is easier because you don't have to worry about stupid shit like convergence. On the other hand, it means throwing away all grounding in reality and admit that you're just playing with symbols in a fancy way. And getting really nice real-world-relevant results from the exercise...

That said, I can imagine meeting space aliens who know how to count but only using generating functions, and the process of matching things to their tentacles to 'count' would be a monstrously hard concept, learned only after decades of schooling... It's a whole different starting point to a whole class of problems.

Speaking of such space aliens, I once saw Richard Stanley give a talk in which generating functions were quite prominent. You can think of the Taylor Series of a trigonometric function as a generating function in itself, and certain of these actually count interesting things. So Stanley was curious about how much of trigonometry you could recover using combinatorics - combining and counting whatever objects it was that these trig functions were generating. The answer, apparently, was quite a lot, so long as you didn't mind that all reference to geometry was lost.

Another race of aliens I like to imagine never deals with integers, except for a few crazy specialists, but instead learn about permutations from an early age and use them for all of their basic mathematical understanding of the world. These aliens never got in to mass production, because for them every object is distinct. You don't have six eggs, you have six objects with all of the properties of eggs, arranged in a particular configuration. And when I switch two of the eggs in the carton, the permutation that describes the eggs has changed...

Ok, enough rambling for now...

posted by kaibutsu at 12:51 PM on April 22, 2010 [1 favorite]

*I was a TA for a serious theoretical computer scientist (the only things on his desk were a legal pad and a #2 pencil -- a computer scientist!).*

Did you TA for Dijkstra? (Which would be seriously badass.)

posted by kmz at 1:11 PM on April 22, 2010

*Did you TA for Dijkstra? (Which would be seriously badass.)*

Hah, no, it was Andy Yao. He has a giant brain. I have a giant

*head*, but I think it's mostly skull.

posted by madmethods at 4:03 PM on April 22, 2010

*1) There's a lot of math that isn't advanced.*

Sure, tons of it!

*2) There's a lot of advanced math that isn't hard.*

Hmm, that's a little more iffy. There's a lot of math where you can get a decent idea of why people are interested but it's still pretty hard to actually

*do*it. Take something like Gödel's Theorem - that's not really "advanced" inasmuch as it's 70 years old and your average undergraduate math student goes through the proof - and you can certainly understand it - but the proof, while quite clear, is pretty hard.

"Advanced" stuff, as in things you don't learn as an undergraduate, that stuff is plain hard to do.

I'm not at all trying to discourage people from studying math - there's tons of fun and you have the huge advantage that many interesting things close to the root of it have been discovered in the last forty years or so. We're also much better at teaching math now, I think.

But there isn't going to be some "Good Will Hunting type [who] will come along and explain maths in one sentence" as doublehappy wrote in his cryptic clew!

posted by lupus_yonderboy at 8:39 PM on April 22, 2010

In brief, the point of generating functions is that they provide techniques for manipulating entire infinite sequences of numbers as single objects.

There are lots of interesting and important sequences of integers in mathematics -- and in combinatorics in particular -- like the Fibonacci sequence and the Catalan numbers. One reason sequences like these are important is because they

Let's say you've figured out a formula for counting some particular kind of thing -- like binary trees, for example -- and now you want to use this knowledge to figure out how to count another, related kind of thing: binary trees whose junctions can be coloured in any of K different ways, for example. In solving the first problem you discovered the Catalan numbers, which go (1, 1, 2, 5, 14, ...). But just having that sequence doesn't help much in solving the second problem. You might have discovered a neat formula for working out the Nth Catalan number (of which there are plenty on the Wikipedia page linked in the OP) -- but again, this might not help you solve your new problem.

What you really want is to have your sequence of numbers expressed in the form of a

John Baez has written a bit about this (e.g."Week 202"), where he emphasizes that generating functions correspond to "structure types", literally types of structure that can be imposed on a finite set.

posted by logopetria at 1:23 AM on April 23, 2010

There are lots of interesting and important sequences of integers in mathematics -- and in combinatorics in particular -- like the Fibonacci sequence and the Catalan numbers. One reason sequences like these are important is because they

*count*things; for example, the number of distinct binary trees with N junctions is just the Nth Catalan number.Let's say you've figured out a formula for counting some particular kind of thing -- like binary trees, for example -- and now you want to use this knowledge to figure out how to count another, related kind of thing: binary trees whose junctions can be coloured in any of K different ways, for example. In solving the first problem you discovered the Catalan numbers, which go (1, 1, 2, 5, 14, ...). But just having that sequence doesn't help much in solving the second problem. You might have discovered a neat formula for working out the Nth Catalan number (of which there are plenty on the Wikipedia page linked in the OP) -- but again, this might not help you solve your new problem.

What you really want is to have your sequence of numbers expressed in the form of a

*generating function*. That's because there are lots of powerful techniques for manipulating and combining generating functions, which is what "generatingfunctionology" is all about. So in the example above, you would take the generating function for the Catalan numbers, and the generating function that encodes "the number of ways to colour something in any of K different colours"; you then combine them in the appropriate way, and what you get is a new generating function that encodes the sequence you're looking for.John Baez has written a bit about this (e.g."Week 202"), where he emphasizes that generating functions correspond to "structure types", literally types of structure that can be imposed on a finite set.

*Being a binary tree*is a type of structure, as is*Being coloured in one of K ways*. From simpler structure types we can construct more complicated ones, like*Being a binary tree whose junctions are coloured any of K ways*, or*Being split into P parts, each of which is a binary tree*. When we combine two structure types like this, there's a corresponding way to combine their generating functions, and so counting the more complex structures becomes much easier.posted by logopetria at 1:23 AM on April 23, 2010

*that's not really "advanced" inasmuch as it's 70 years old*

I think we are using different definitions for "advanced". You are using it as a distance backwards from the most recent thing known, I am using it as a distance forward from the first thing known.

Maybe you don't realize or aren't thinking about how innumerate the general public is. To them,

**algebra**is "advanced". In fact, I've more than once astounded

**other computer programmers**, people who should be able to do this themselves, by doing

**simple arithmetic**in my head.

*"Advanced" stuff, as in things you don't learn as an undergraduate,*

But even by your definition, there is still a lot of non-undergraduate math that's pretty easy. A non-math-major undergraduate might take calculus. They never cover basic topology, vector calculus, linear algebra and many other relatively easy subjects.

posted by DU at 4:49 AM on April 23, 2010 [1 favorite]

« Older Washable walls | 'cause bobody knows fascism like a fascist. Newer »

This thread has been archived and is closed to new comments

Does anyone else download and appreciate papers/books like this even though they struggle with even basic concepts? I love the abstracts of math papers but, as soon as they flop out the greek letters, I'm out. One day some Good Will Hunting type will come along and explain maths in one sentence for me but, until then, I'll just appreciate the aesthetics, I guess.

posted by doublehappy at 1:17 AM on April 22, 2010 [1 favorite]