Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $a_n$ is the number of orderly divisions of set $\left\{ 1,2,...,n \right\}$ (which means that the sequence of blocks is important, but not the order of elements in blocks). Prove that: $\displaystyle \sum_{k}\left[n\atop k\right]a_k=n!2^{n-1}$ for $n\ge 1$.

Is it possible to prove this by induction on $n$? I think combinatorial interpretation will be easier way, but I don't know how to do that.

share|improve this question
    
There is an algebraic answer to this question at this MSE link. –  Marko Riedel Jun 4 at 2:22

2 Answers 2

up vote 3 down vote accepted

I managed to find a more direct combinatorial argument. $n!\,2^{n-1}$ is the number of ways to choose a permutation $\pi$ of $[n]$ and insert bars in any subset of the spaces between the elements of the permutation. In other words, it counts the strings of the form $$\pi_1\mid\pi_2\mid\dots\mid\pi_k\tag{1}$$ such that $\pi=\pi_1\dots\pi_k$ and $|\pi_i|>0$ for $i=1,\dots,k$.

Let $\sigma=\pi_1\mid\pi_2\mid\dots\mid\pi_k$ by such a string, and consider a $\pi_i=a_1a_2\dots a_m$, say. Break $\pi_i$ into segments in the following way. The first segment begins with $a_1$. If $a_1=\max\{a_j:j=1,\dots m\}$, there is only one segment, $\pi_i$. Otherwise, the second segment begins with the first $a_j$ larger than $a_1$. Continue in this fashion: $a_j$ begins a new segment iff $a_j>a_\ell$ for all $\ell<j$. Now reinterpret each of these segments as a cycle, $\pi_i$ as an unordered set $A_i$ of disjoint cycles, and $\sigma$ as a sequence $\langle A_1,\dots,A_k\rangle$ of $k$ unordered sets of cycles that collectively exhaust $[n]$. Let $S$ be the set of such $\langle A_1,\dots,A_k\rangle$; clearly from each $\langle A_1,\dots,A_k\rangle\in S$ we can reconstruct the corresponding $\pi$ of form $(1)$, so $|S|=n!\,2^{n-1}$.

For $1\le\ell\le n$ let $S_\ell$ be the set of $\langle A_1,\dots,A_k\rangle\in S$ such that $A_1\cup\dots\cup A_k$ contains $\ell$ cycles. $\left[n\atop \ell\right]$ is the number of ways to partition $[n]$ into $\ell$ parts and assign a cyclic order to each part, so it is simply the number of sets $\{\sigma_1,\dots,\sigma_\ell\}$, where the $\sigma_i$ are disjoint cycles whose union is $[n]$. Then $a_\ell$ is the number of orderly divisions $\langle A_1,\dots,A_k\rangle$ of $\{\sigma_1,\dots,\sigma_\ell\}$. Thus, $\left[n\atop\ell\right]a_\ell$ is the number of ways to break $[n]$ into $\ell$ cycles, partition the set of cycles, and order the partition, i.e., $\left[n\atop\ell\right]a_\ell=|S_\ell|$. Since $S=\bigcup\limits_{\ell=1}^nS_\ell$, and the $S_\ell$ are pairwise disjoint, it follows that $$n!\,2^{n-1}=\sum_{\ell=1}^n\left[n\atop\ell\right]a_\ell\;,$$ as desired.

share|improve this answer

I failed to see a direct combinatorial interpretation, but (IMHO) I found a combinatorially satisfying derivation nevertheless (induction seemed unnatural to me). First, my conventions:

  • $\displaystyle\left[a\atop b\right]$: Stirling numbers of the 1st kind; counts permutations of $a$ items with $b$ disjoint cycles.
  • $\displaystyle\left\{a\atop b\right\}$: Stirling numebrs of the 2nd kind; counts partitions of $a$ items into $b$ nonempty subsets.
  • $L(a,b)$: Lah numbers; counts partitions of $a$ items into $b$ (internally) ordered subsets.

The number of ways to partition $[k]=\{1,2,\cdots,k\}$ into $\ell$ cells, the cells collectively ordered but not internally, is given by $\ell!\left\{k\atop \ell\right\}$ via inspection. Summing over $\ell$ yields

$$a_k=\sum_{\ell=1}^k \ell! \left\{k\atop\ell\right\}. \tag{1}$$

Plugging this into the left-hand side of the given formula and rearranging yields

$$F=\sum_{k=0}^n \left[n\atop k\right]a_k=\sum_{k=0}^n \left[n\atop k\right] \left(\sum_{\ell=1}^k \ell!\left\{k\atop\ell\right\}\right)=\sum_{\ell=1}^n \ell!\left(\color{Purple}{\sum_{k=\ell}^n\left[n\atop k\right]\left\{k\atop\ell\right\}}\right) \tag{2}$$

We seek a combinatorial interpretation of the sum in purple. The 1st kind of Stirling numbers counts permutations in $S_n$ with $k$ disjoint cycles ($\pi=\tau_1\cdots\tau_k$), and after multiplying by the 2nd kind of Stirling number we are counting "refinements" of these permutations into $\ell$ subsets, each subset containing at least one of $\pi$'s cycles. For example, for $\pi=(12)(34)(56)(789)$ one of these collections of three subsets containing its cycles would be $\{(12),(789)\},\{(34)\},\{(56)\}$.

Notice that sets of disjoint cycles are in bijection with the products of those cycles, so we can instead interpret this as counting the number of collections of $\ell$ singleton sets of disjoint permutations, the total number of items the permutations acting on being $n$. Equivalently, for each set partition $\Gamma$ of the set $[n]=\{1,2,\cdots,n\}$ into $\ell$ disjoint subsets, we count the number of permutation collections

$$\{\sigma_\gamma\in S_{\gamma}:\gamma\in\Gamma\}, \tag{$*$}$$

where each $\gamma$ is a cell of the partition $\Gamma$ and $S_\gamma$ is its permutation group, and then summing over all the $\ell$-part set partitions $\Gamma$ of $[n]$. But for $\Gamma$ fixed, recall that permutations of a set $\gamma$ are in bijection with ways of ordering the elements of $\gamma$; ultimately we are counting the number of ways to partition $[n]$ into $\ell$ internally ordered sets, the Lah numbers! Therefore we obtain

$$F=\sum_{\ell=1}^n\ell! \color{Purple}{L(n,\ell)}.$$

This is the final stretch, and it is not difficult. For each partitioning of $[n]$ into $\ell$ internally ordered subsets (counted by the Lah numbers), we can multiply by $\ell!$ to further count the number of partitions of $[n]$ into $\ell$ subsets ordered both internally and externally. This is equivalent to ordering sequentially the elements of $[n]$ and placing precisely $\ell-1$ bars $|$ in between them to separate them into blocks (there are precisely $n-1$ implicit spaces between the numbers to put the bars).

Of course, there are $n!$ sequential arrangements and independently there are $2^{n-1}$ subsets of the set of all spaces between the numbers to place the bars. Thus, $F=n!\,2^{n-1}$.

share|improve this answer
    
Very nice, but there's a small error at the end: to get $\ell$ blocks you want $\ell-1$ bars |. –  Brian M. Scott May 8 '12 at 21:03
    
@BrianM.Scott: Thanks! –  anon May 9 '12 at 5:22
    
You might be interested in my answer: I found a more direct combinatorial argument. –  Brian M. Scott May 9 '12 at 17:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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