# 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 $i$th 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