# Counting ways to arrange envelopes by inclusion (from Stanley's Enumerative Combinatorics)

This is a question from supplement( Bijective proof problems ) to the Stanley's Enumerative Combinatorics.

The question statement goes like this.

"In how many ways can $n$ square envelopes of different sizes can be arranged by inclusion. For instance, with $6$ envelopes $A, B, C, D, E, F$( listed in decreasing order of their sizes), one way of arranging them would be $F \in C \in B$, $E \in B, D \in A$, where $I \in J$ means envelope $I$ is placed in envelope $J$".

I could not come up with a bijection( had no clue ).

I tried in to write a recurrence relation as following.

let, $F_n$ = Total number of arrangements possible with $n$ envelopes. Assume $F_0 = 1$.

$$F_n = F_{n-1} + \binom{n-1}{1} F_{n-2} + \binom{n-1}{2} F_{n-3} + \binom{n-1}{3} F_{n-4} +\cdots + \binom{n-1}{n-1} F_0$$

The thought process was, smallest envelope can be grouped with no other envelope($F_{n-1}$ term) or with one other letter($\binom{n-1}{1}F_{n-1}$ term) or with $2$ other letters .... $n-1$ other letters.

my notion of grouping is inclusion. Letters $i, j, k$ are grouped means the smallest letter is included in second smallest, second smallest letter is included in the third smallest etc. So, given a set of $k$ letters we include them in one another(we can do it in only one way).

Grouping smallest letter with $i$ other chosen letters$\binom{n}{i}$, we're left with $n-i-1$ letters to arrange. Hence the term $F_{n-i-1}$.

-

First of all, thanks to Gerry Myerson for (incorrectly) counting the configurations for $n=4$ and (correctly) suggesting the formula $F_n=n!$, which is indeed the right one.

Second, the objects we are looking at are labelled rooted forests with $n$ nodes, in which labels are compatible with the tree structure (a parent label is always less than any child label); the parent-child relation corresponding to inclusion of envelopes.

Third, I don't understand what the solution suggested in the question is (notably I don't understand the "grouped with" relation or why it would characterise the inclusion structure of envelopes) and I therefore don't think it is correct (and in any case the written formula fails for $n=3$ where $f_3=6\neq2+2+1$). But the idea of focussing on the smallest envelope is quite fruitful, and leads to a proof simpler than the one I found originally (which was based on focussing on the largest envelope). Leaving out the smallest envelope from a valid arrangement always gives a valid arrangement of the remaining envelopes, so let us see what extra information is needed to reconstruct the full arrangement from that. It turns out that it suffices to know (the label of) the envelop immediately containing the smallest envelope (the parent node of this leaf node), which could be any one of the remaining envelopes, or it could be undefined because the smallest envelope is not contained in anything. So regardless of what arrangement of $n-1$ envelopes one has, it can be extended in $n$ different ways to one of $n$ envelopes: $n-1$ way to put the smallest envelope into another one, and $1$ way to add it as a singleton. This leads to the recurrence $F_n=nF_{n-1}$, which you know how to solve.

Next, how to turn this into a bijection with permutations of $n$? Given such a permutation $\sigma$, the most obvious way to associate one of $n$ values to the final number $n$ is to take the image $\sigma_n=\sigma(n)$ of $n$. If we want to take that as label of the parent of $n$, then the case $\sigma_n=n$ that $n$ is a fixed point presents itself naturally as candidate to correspond to arrangements with envelope $n$ as singleton; in this case removing $n$ leaves a permutation of $n-1$ and we can continue recursively with that. If $\sigma_n\neq n$ then we take envelope $n$ to be directly included in envelope $\sigma_n$, but we need to do something to get a permutation $\sigma'$ of $n-1$ to continue with recursively. The most obvious way to do so it to cut the number $n$ out of its cycle: the number $i=\sigma^{-1}(n)$ that maps under $\sigma$ to $n$ will get $\sigma'(i)=\sigma(n)$, and for all other $i<n$ one keeps $\sigma'(i)=\sigma(i)$ (in cycle the notation for $\sigma$ this just means scrapping the number $n$). Now we can continue recursively with $\sigma'$, and this gives our bijection (as the process is step-by-step reversible).

Here is an example of the computation, for $n=9$ and (in cycle notation) $\sigma=(1~6~3~8)(2)(4~9~7~5)$. Put $9$ into $\sigma_9=7$, and $\sigma'=(1~6~3~8)(2)(4~7~5)$. Then put $8$ into $1$, and $\sigma''=(1~6~3)(2)(4~7~5)$. Continuing like this one successively finds $7\in5$, $6\in3$, $5\in4$, $4$ is a root (external envelope), $3\in1$, and finally $2$ and $1$ are roots. So each cycle of $\sigma$ determines a tree in the forest with those labels, the minimal element in each cycle is a root, and every other element $i$ has as parent the first element with number less than $i$ (for a larger envelope) reached from $i$ within its cycle (i.e., by iterating $\sigma$ starting from $i$).

-
perfect. Thanks a lot. Regarding the solution proposed in the question, i was thinking like Gerry at that time( but, now i checked the question once again and you're right ). I'm still interested in what happens in that case. I'll read about Bell numbers and see. –  Novice Mar 10 '13 at 8:30

We can treat each placement of $n$ envelopes as a function $f:\{1,\ldots,n\}\rightarrow\{0,\ldots,n\}$, where $f(i)$ is the number of the envelope immediately containing $i$-th envelope (1 is the biggest, $n$ is the smallest envelope), or 0 if $i$-th envelope is not contained in any other. It must be $f(i)<i$ for all $i$, so we have exactly $i$ choices for the value of $f(i)$. Hence there are $n!$ such functions, and it is easy to see that the correspondence between placements and functions is a bijection.

-

I think you'll find that these are the Bell numbers. A starting point is at the Online Encyclopedia of Integer Sequences.

-
I don't agree. For $n=3$ I find $6$ solutions. Notably there are $2$ solutions where the symmetric transitive closure of containment relates all three envelopes: on one hand $C\in B\in A$, and on the other hand $B,C\in A$ but $C\notin B$. –  Marc van Leeuwen Mar 8 '13 at 13:20
@Marc, my interpretation was that if two envelopes were inside a third then one of the two had to be inside the other, but I now see the statement of the problem does not force that interpretation on us. With your interpretation, I count 23 for $n=4$. If I've missed one, we may be talking about the factorials, but I don't see the bijection. –  Gerry Myerson Mar 9 '13 at 0:40
@GerryMyerson, I was thinking the same. After reading the comment by Marc i checked the question once again( in the supplement ) and found out that i was wrong( please look at the modified example in question statement ). But, anyway, we're solving another problem, then. I'll read about Bell numbers. Thanks. –  Novice Mar 10 '13 at 8:10