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?


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$ – ante.ceperic Aug 25 '13 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.