Let $a_k$ be the number of ways to partition a set of $n$ elements $orderly$,
which means that order of subsets matters, but order of elements in each subset does not.

My task:

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

The only thing I got so far is:

$$a_k = \sum_{i=1}^{k} \left\{n\atop k\right\} \frac{1}{i!}$$

I tried to change the order of this sum $\sum\limits_{k=1}^n \left[n\atop k\right]\sum\limits_{i=1}^{k} \left\{n\atop k\right\} \frac{1}{i!}$

and got something like that: $\sum\limits_{k=1}^n \frac{1}{k!}\sum\limits_{i=k}^{n} \left[n\atop i\right]\left\{i\atop k\right\}$

My next idea was combinatorial proof, but either I cannot think of one, or I made some crucial mistake above, which makes my efforts pretty useless.

Can anyone guide me how to do this task?
I'd also be most thankful for correcting my mistakes - I'd rather make them here than on my exam sheet...


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\}$$

  • $\begingroup$ There was a typo in my question as well, but of course I confused $i!$ with $\frac{1}{i!}$. You've been very helpful, thanks a lot! $\endgroup$ – sr. Aug 19 '12 at 18:01

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.