I was searching for a combinatorial proof $x(x+1) \dots (x+n-1) = \sum_k|s(n,k)| x^k$. Is there a set with cardinality equal to the left hand and by rule of sum, we could show that the right hand equals to the left hand?
Asked
Active
Viewed 23 times
0
-
Yes. After dividing both sides by $n!$, the LHS is the number of multisets of size $n$ from a set of size $x$. The RHS can then be obtained by counting these multisets using Burnside's lemma: https://math.stackexchange.com/questions/3361649/counting-number-of-groupings-using-group-actions/3361677#3361677 – Qiaochu Yuan Oct 23 '23 at 18:10