In case anyone is interested, here’s a combinatorial proof for the cycle generating function identity that I like (inspired by the http://en.wikipedia.org/wiki/Chinese_restaurant_process):

Imagine a restaurant with an infinite number of (unlabeled) tables that serves dishes, where all the customers at a given table have the same dish. A seating arrangement for customers tells us who customer sits next to (say, to the left of) for each . (If a customer is seated at her own table, then she sits to the left of herself.) A dish assignment is a choice of one of the dishes for each of the tables with customers seated at it. The left-hand side and the right-hand side of the equation both count the number of ways to specify a seating arrangement and a dish assignment for customers.

On the left-hand side, we pick the number of tables (), choose a seating arrangement for the customers at the tables ( ways, since the seating arrangement at each table is a cycle), and pick a dish for each of the tables ( ways, since there are dishes to choose from). The total number of seating arrangements/dish assignments produced by this procedure is thus .

On the right-hand side, we seat the customers one by one: The first customer entering the restaurant must sit at a table by herself, while each subsequent customer can either sit at a new table by herself or to the left of an already-seated customer. If a customer sits at a new table, she must choose a dish, while if she sits at a table that already has at least one customer, she has the dish that the first customer to sit at that table ordered. So the first customer has choices (she must sit at a new table, and she must then choose one of the dishes), the second customer has choices (she can either sit at a new table, in which case she must choose one of the dishes, or she can sit to the left of the first customer), and, in general, the th customer has choices (she can sit at a new table and order one of the dishes or she can sit to the left of one of the customers already seated and have what they’re having). Hence the total number of seating arrangements/dish assignments produced by this procedure is .

So the two polynomials agree for all integers , and thus they must agree for all .

David

### Like this:

Like Loading...

*Related*

Nice! I was thrown off thinking about the left hand side and the possibility of there being empty seats between people, but this assumes there aren’t empty seats, right? And if two polynomials agree for infinitely many points, then they are equal!… can you explain/lead me to the proof? Sorry if it’s obvious.

Yeah, ignore empty seats. (I guess I sort of imagine that a new seat magically appears when a new customer decides to sit at a given table.)

As for the fact about polynomials, it comes from the fact that a polynomial with degree n has at most n roots: If two polynomials agree for infinitely many points, then the polynomial you get when you subtract one from the other has infinitely many roots, so it must be the zero polynomial, which means that the two polynomials are equal.