# Is there a combinatorial proof of this binomial-type formula involving Stirling numbers?

Suppose $$\partial$$ and $$t$$ are elements of a noncommutative ring which satisfy $$[\partial,t]=1.$$ Then one can show using an induction argument that $$$$(t\partial)^k=\sum_{i=0}^k{k \brace i}t^i\partial^i,$$$$ where $${k \brace i}$$ denotes the Stirling numbers of the second kind. The argument just uses the resursive formula satisfied by the $${k \brace i}.$$ A combinatorial definition of $${k \brace i}$$ is that it is the number of ways to form $$i$$ disjoint nonempty subsets from a set of size $$k.$$ This came up in my research on $$D$$-modules. In this setting it's straightforward and kind of fun to have this operator act on certain functions and deduce identities involving these Stirling numbers.

My questions is: is there a combinatorial proof of this identity using only the combinatorial definition? I'm looking for something similar to the proof of the binomial theorem which basically says: "Every $$a^kb^{n-k}$$ term in $$(a+b)^n$$ comes from choosing $$k$$ of the $$n$$ $$a$$'s and letting the rest of the terms in the product be $$b$$'s. Then the coefficient of $$a^kb^{n-k}$$ is the number of ways to choose $$k$$ $$a$$'s, hence is $${n\choose k}.$$"

I've spent a long time trying to somehow come up with a clever partition of a set with $$k$$ elements for each copy of $$t^i\partial^i$$ that appears in the sum, but I can't seem to come up with anything.

For what it's worth, I'm just asking this question for fun.

Yes, you can look at how the LHS and RHS act on polynomials, or equivalently on power series / generating functions. $$(t \partial)^k$$ is the operator which sends $$t^n$$ to $$n^k t^n$$, and $$t^k \partial^k$$ is the operator which sends $$t^n$$ to $$(n)_k t^n$$ where $$(n)_k = n(n-1) \dots (n-k+1)$$ is the falling factorial. That means this identity is equivalent to the identity
$$n^k = \sum_{i=0}^k {k \brace i} (n)_i$$
which has a straightforward combinatorial proof: the LHS is the number of functions $$[k] \to [n]$$ from a $$k$$-element set to an $$n$$-element set, and the RHS splits up the count of such functions according to the size of their image. A function $$f : [k] \to [n]$$ whose image has size $$i$$ is determined by
• the partition of $$[k]$$ determined by the preimages of $$f$$, which is a partition into $$i$$ nonempty subsets and hence which is counted by $${k \brace i}$$, together with
• the assignment of each subset in the partition to a distinct element of $$[n]$$, which is counted by $$(n)_i$$.