Combinatorial Proof for Cycle g.f. Identity

In case anyone is interested, here’s a combinatorial proof for the cycle generating function identity \sum_{k = 1}^n c(n,k) x^k = x (x + 1) \cdots (x + n - 1) 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 x dishes, where all the customers at a given table have the same dish. A seating arrangement for n customers tells us who customer i sits next to (say, to the left of) for each 1 \le i \le n. (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 x 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 n customers.

On the left-hand side, we pick the number of tables (1 \le k \le n), choose a seating arrangement for the n customers at the k tables (c(n,k) ways, since the seating arrangement at each table is a cycle), and pick a dish for each of the k tables (x^k ways, since there are x dishes to choose from). The total number of seating arrangements/dish assignments produced by this procedure is thus \sum_{k = 1}^n c(n,k) x^k.

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 x choices (she must sit at a new table, and she must then choose one of the x dishes), the second customer has x + 1 choices (she can either sit at a new table, in which case she must choose one of the x dishes, or she can sit to the left of the first customer), and, in general, the ith customer has x + (i - 1) choices (she can sit at a new table and order one of the x dishes or she can sit to the left of one of the i - 1 customers already seated and have what they’re having). Hence the total number of seating arrangements/dish assignments produced by this procedure is x (x + 1) \cdots (x + n - 1).

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

 

David

 

Advertisements

2 comments

  1. 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.

    • dgklein

      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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: