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

Question

Suppose $\partial$ and $t$ are elements of a noncommutative ring which satisfy $[\partial,t]=1.$ Then one can show using an induction argument that \begin{equation} (t\partial)^k=\sum_{i=0}^k{k \brace i}t^i\partial^i, \end{equation} 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.

Answer 1

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$.