Sum of Stirling numbers of both kinds

Solution 1:

Here’s a combinatorial argument to show that

$$\sum_{k=1}^n \left[n\atop k\right] a_k = n!2^{n-1}\;,$$

where $\left[n\atop k\right]$ is the number of permutations of $[n]=\{1,\dots,n\}$ having $k$ cycles, and $a_k$ is the number of orderly partitions of those $k$ cycles.

First, $n!2^{n-1}$ is clearly the number of ways of breaking a permutation of $[n]$ ($=\{1,\dots,n\}$) into segments by inserting breakpoints between neighboring elements of the partition; the number of segments may be anywhere from $1$ (no breakpoints) through $n$ ($n-1$ breakpoints).

Now consider such a segmented partition. For example, with $n=9$ we might have $$31\mid6259\mid478\;.\tag{1}$$ Each segment will correspond to an unordered set of cycles. To break a segment into cycles, mark each number in the segment that is larger than all of its predecessors within the segment: $$\underline{3}1\mid\underline{6}25\underline{9}\mid\underline{4}\underline{7}\underline{8}\;.$$ Clearly the first number in each segment will be marked. The substring from a marked number up to but not including the next marked number or the end of the segment is a cycle: $$(\underline{3}1)\mid(\underline{6}25)(\underline{9})\mid(\underline{4})(\underline{7})(\underline{8})\;.$$ The segmented partition $(1)$ thus corresponds to the $3$-tuple $\left\langle\{(31)\},\{(625),(9)\},\{(4),(7),(8)\}\right\rangle$ of sets of cycles partitioning the $6$ cycles of the permutation $(31)(4)(625)(7)(8)(9)$. This is one of the orderly partitions counted by the term $\left[9\atop 6\right]a_6$ of the sum $\sum_{k=1}^9\left[9\atop k\right]a_k$.

Conversely, if $\langle\{13\},\{(9),(526)\},\{(7),(8),(4)\}\rangle$ is an orderly partition of $[9]$, we can reconstruct the corresponding segmented permutation as follows. First insert the segmentation corresponding to the sets in the partition: $$(13)\mid(9)(526)\mid(7)(8)(4)\;.$$ Within each segment mark each number that is the largest number in its cycle: $$(1\underline{3})\mid(\underline{9})(52\underline{6})\mid(\underline{7})(\underline{8})(\underline{4})\;.$$ Rotate each cycle to bring the largest number to the front: $$(\underline{3}1)\mid(\underline{9})(\underline{6}52)\mid(\underline{7})(\underline{8})(\underline{4})\;.$$ Within each segment rearrange the cycles in descending order of maximal element: $$(\underline{3}1)\mid(\underline{6}52)(\underline{9})\mid(\underline{4})(\underline{7})(\underline{8})\;.$$ Finally, erase the markings and the parentheses, leaving only the segmentation: $$31\mid6529\mid478\;.$$

A bit of thought will show that these operations do define in general a bijection between segmented permutations and orderly partitions of the cycles of permutations of $[n]$.

There are a couple of errors in your computations.

$\left\{k\atop i\right\}$ is the number of partitions of $k$ distinguishable objects into $i$ non-empty sets when neither the order within the subset nor the order of the subsets matters. Thus, the number of orderly partitions is $\sum_{i=1}^k\left\{k\atop i\right\}i!$, not $\sum_{i=1}^k\left\{k\atop i\right\}\frac1{i!}$. The desired sum is then

$$\sum_{k=1}^n\sum_{i=1}^k\left[n\atop k\right]\left\{k\atop i\right\}i!=\sum_{i=1}^ni!\sum_{k=i}^n\left[n\atop k\right]\left\{k\atop i\right\}$$

Solution 2:

Start by observing that the species of orderly partitions has the specification $$\mathfrak{S}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z})).$$ This gives the bivariate generating function $$G(z, u) = \frac{1}{1-u(\exp(z)-1)}.$$

Hence the generating function of the $a_n$ is $$G(z) = G(z, 1) = \frac{1}{2-\exp(z)} = \frac{1}{2} \frac{1}{1-\exp(z)/2}.$$

Substituting this into the sum yields $$\sum_{k=1}^n \left[n\atop k\right] k! [z^k] \frac{1}{2} \frac{1}{1-\exp(z)/2}.$$

Call this sum $P_n$ and introduce the exponential generating function $$P(z) = \sum_{n\ge 1} P_n \frac{z^n}{n!}.$$

We have for the sum that $$\sum_{k=1}^n \left[n\atop k\right] k! [z^k] \frac{1}{2} \frac{1}{1-\exp(z)/2} = \frac{1}{2} \sum_{k=1}^n \left[n\atop k\right] k! [z^k] \sum_{q\ge 0} \frac{\exp(qz)}{2^q} \\= \frac{1}{2} \sum_{k=1}^n \left[n\atop k\right] \sum_{q\ge 1} \frac{q^k}{2^q}.$$

This gives for $P(z)$ that $$P(z) = \frac{1}{2}\sum_{n\ge 1} \frac{z^n}{n!} \sum_{k=1}^n \left[n\atop k\right] \sum_{q\ge 1} \frac{q^k}{2^q} = \frac{1}{2} \sum_{q\ge 1} \sum_{k\ge 1} \frac{q^k}{2^q} \sum_{n\ge k} \left[n\atop k\right] \frac{z^n}{n!}.$$

Recall that the species for Stirling numbers of the first kind is given by $$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{\ge 1}(\mathcal{Z})).$$ This gives the bivariate generating function $$H(z, u) = \exp\left(u\log\frac{1}{1-z}\right).$$

Substituting this into $P(z)$ yields $$\frac{1}{2} \sum_{q\ge 1} \sum_{k\ge 1} \frac{q^k}{2^q} \sum_{n\ge k} \frac{z^n}{n!} n! [z^n] [u^k] \exp\left(u\log\frac{1}{1-z}\right) \\ =\frac{1}{2} \sum_{q\ge 1} \sum_{k\ge 1} \frac{q^k}{2^q} \sum_{n\ge k} z^n [z^n] \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k.$$

Now the innermost sum annihilates the coefficient extractor so we get $$\frac{1}{2} \sum_{q\ge 1} \sum_{k\ge 1} \frac{q^k}{2^q} \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k = \frac{1}{2} \sum_{q\ge 1} \frac{1}{2^q} \left(-1 + \exp\left(q\log\frac{1}{1-z}\right)\right) \\ = -\frac{1}{2} + \frac{1}{2} \sum_{q\ge 1} \frac{1}{2^q} \left(\frac{1}{1-z}\right)^q = -\frac{1}{2} + \frac{1}{2} \frac{1/2/(1-z)}{1-1/2/(1-z)} \\ = -\frac{1}{2} + \frac{1}{2} \frac{1}{2(1-z)-1} = -\frac{1}{2} + \frac{1}{2} \frac{1}{1-2z}.$$

The conclusion is that $$P_n = n! [z^n] P(z) = n! [z^n] \frac{1}{2} \frac{1}{1-2z} = n! \times \frac{1}{2} \times 2^n = 2^{n-1} n!$$ as claimed.

Another computation that refererences Wilf's generatingfunctionology. Remark, somewhat later. The annihilated coefficient extractor is not strictly necessary here, we may also recognize the EGF by inspection.