Proving an identity relating the number of linearly ordered partitions to Stirling numbers

Question

For $n,k\in N_0$, let $L(n,k)$ be the number of ways a set of $n$ elements can be partitioned into $k$ nonempty linearly ordered subsets. I want to prove that for $n,k\in N_0$,

$L(n,k)=\sum_{i=0}^nc(n,i)S(i,k)$,

where $c(n,k)$ and $S(n,k)$ are the unsigned Stirling numbers of the first and second kind respectively.

I know how the Stirling numbers are defined and what they count but I've never seen them appear together in an identity like this. I have proved recurrence relations for them individually but not as a product. I'm not sure how to proceed.

Answer 1

Instead of thinking of $L(n,k)$ as the number of ways to partition $\{1,\dots,n\}$ into $k$ nonempty sets, and then linearly order each set, think of $L(n,k)$ as the number of ways to partition $\{1,\dots,n\}$ into $k$ nonempty sets, and then choose a permutation for each set. These are obviously the same thing, but it is helpful to think of the things as permutations, since permutations are just collections of cycles, which helps to explain the $c(n,i)$ part.

So, in the summation $\sum_{i=0}^n c(n,i)S(i,k)$, the $c(n,i)$factor gives the number of ways to partition $\{1,\dots,n\}$ into $i$ parts, and then put a cyclic ordering on each part. We now have $i$ things (cycles), and a factor of $S(i,k)$, which suggests that we are then partitioning these $i$ cycles into $k$ parts. When you have done these two things, we know have partitioned $\{1,\dots,n\}$ into $k$ parts, where each part is a disjoint union of several cycles, each made of numbers from $\{1,\dots,n\}$. This means that each part is a permutation on a nonempty subset of $\{1,\dots,n\}$ (because a permutation is just a collection of disjoint cycles), which is exactly what is desired.

Answer 2

The combinatorial class of partitions into linearly ordered subsets is given by

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

Therefore we have

$$L(n,k) = 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}.$$

On the other hand we have

$$\sum_{q=0}^n {n\brack q} {q\brace k} \\ = n! [z^n] \sum_{q=0}^n \frac{1}{q!} \left(\log\frac{1}{1-z}\right)^q q! [w^q] \frac{1}{k!} (\exp(w)-1)^k$$

Now since $\log\frac{1}{1-z} = z +\cdots$ we may extend $q$ to infinity because there is no contribution to $[z^n]:$

$$\frac{n!}{k!} [z^n] \sum_{q\ge 0} \left(\log\frac{1}{1-z}\right)^q [w^q] (\exp(w)-1)^k \\ = \frac{n!}{k!} [z^n] \left(\exp\log\frac{1}{1-z} -1\right)^k = \frac{n!}{k!} [z^n] \frac{z^k}{(1-z)^k}.$$

We may stop here because we have obtained the same closed form as from the partitions into ordered subsets, which is the claim. These are known as Lah numbers.

For a combinatorial argument, we are splitting $[n]$ into $q$ cycles, then creating $k$ sets of cycles from these. Now for each such set mark the smallest element on each oriented cycle as our start point, then arrange the cycles with the start points in descending order. The linear ordering then results from listing the elements of the ordered cycles starting at the mark of the first cycle, followed by the rest of the first cycle (in order), the second and so on. To see that this is a bijection suppose we have a linear ordering of $p$ values. We mark the first element and scan till we see another that is smaller, mark that one and repeat. The segments following the marks together with the leading mark lets us recover the set of cycles.