Solving through Lovász' Combinatorial Problems and Exercises I found an exercise asking me to prove two identities:

$$ \sum_{k = 0}^n {n \brace k} (x)_n = x^n $$ $$ \sum_{k = 0}^n \left[ n \atop k \right] x^k = x^{(n)}$$

(Notation note: I'm using Pochhamer symbols, brackety ones are cyclic Stirling numbers and curly ones are partition Stirling numbers)

First one yields itself to a combinatorial proof, basically a combinatorial interpretation of the fact that every function can be ''transformed'' into a surjection if we restrict its codomain.

I was able to prove second one using generating functions, but I was unable to find a combinatorial proof. Due to obvious analogies between two identities (writing powers like a sum of falling factorials/ writing rising factorials like a sum of powers) I'm curious is there a combinatorial proof to the second identity?


1 Answer 1


Yes. I give one in this previous math.SE question. (Apparently you can't close a question as duplicate when there's a bounty on it?)

  • $\begingroup$ It's weird, I just started reading your blog post about Polya's enumeration theorem, so if I just waited a little bit longer with that bounty... :D $\endgroup$ Aug 25, 2013 at 9:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .