Line up objects in each box after using Stirling number of second kind?

Solution 1:

In the language of combinatorial classes from Analytic Combinatorics we have Stirling numbers of the first kind, counting sets of cycles, Stirling numbers of the second kind, counting sets of sets and Lah numbers counting sets of tuples, where the cycles, sets and tuples always contain at least one element. We get the class specifications

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\mathcal{U}\times\textsc{CYC}_{\ge 1}(\mathcal{Z})),\; \textsc{SET}(\mathcal{U}\times\textsc{SET}_{\ge 1}(\mathcal{Z})),\; \textsc{SET}(\mathcal{U}\times\textsc{SEQ}_{\ge 1}(\mathcal{Z}))$$

giving the bivariate GFs

$$\exp\left(u\log\frac{1}{1-z}\right),\; \exp(u(\exp(z)-1)),\; \exp\left(u\frac{z}{1-z}\right).$$

We get for Lah numbers the closed form

$$n! [z^n] [u^k] \exp\left(u\frac{z}{1-z}\right) = n! [z^n] \frac{1}{k!} \frac{z^k}{(1-z)^k} \\ = \frac{n!}{k!} [z^{n-k}] \frac{1}{(1-z)^k} = \frac{n!}{k!} {n-1\choose k-1}.$$