I'm trying to come up with a combinatorial proof that $$x^{\overline{n}} = \sum_{k = 0}^n s(n, k)x^k$$ where $s(n,k)$ is the stirling number of the first kind.
Now, $x^{\overline{n}}$ counts the number of ways to put $n$ distinct objects in $x$ distinct boxes if each box can contain any number of objects and the order of the objects in each box matters, so I'm trying to get the sum to count that too. My idea is that you can have anywhere from $0$ to $n$ of the $x$ boxes contain objects and, for any $k$ in that range, we can distribute the objects by first arranging the objects in $k$ circles (there are $s(n,k)$ ways to do that), then placing each of the $k$ cycles in one of the $x$ boxes (there are $x^{\underline{k}}$ ways to do that), and then turning each of the $k$ cycles into a permutation (for a cycle containing $m$ objects, there are $m$ ways to do that). If I can somehow show that $$x^{\underline{k}}\cdot [\text{the product of the number of objects in each cycle}] = x^k$$ then this will work. But that doesn't seem possible. Is there any way to salvage this proof?
