# Combinatorics-one-to-one correspondence between permutations and towers

Find a one-to-one correspondence between the permutations of the set $\{1, 2,\dots,n\}$ and the towers $A_0 \subsetneq A_1 \subsetneq A_2 \subsetneq\dots \subsetneq A_n$, where $\vert A_k\vert = k$ for $k = 0, 1, 2,\dots,n$.

The permutations of the set $\{1, 2,\dots,n\}$ should be $n!$:

There are $n$ ways to assign $1$st element, There are $n-1$ ways to assign $2$nd element, .... There is $1$ way to assign $n$th element

$\Rightarrow n!$ permutations

But the number of proper subsets of a set should be $2^n-1$ which is not equal to $n!$

-
You're not reading the description of what a tower is properly. – Qiaochu Yuan Sep 20 '11 at 3:23
What is a tower? This is the whole question, so this is all the information I know. I tried to look up "towers" but keep getting the Towers of Hanoi. – Gbean Sep 20 '11 at 3:38
It’s defined in the statement of the problem: it’s a sequence of sets satisfying certain constraints involving inclusions and cardinalities. – Brian M. Scott Sep 20 '11 at 3:40

## 1 Answer

As Qiaochu said, you’ve misread the definition of tower. Here’s an example of a tower when $n=3$: $$\varnothing\subsetneq\{2\}\subsetneq\{2,3\}\subsetneq\{1,2,3\}.$$ Can you find a permutation of $\{1,2,3\}$ to which it naturally corresponds? HINT: How was it built up?

Added: Here are all of the towers for $n=3$, each paired with the corresponding permutation:

$$\begin{matrix} \varnothing\subsetneq\{1\}\subsetneq\{1,2\}\subsetneq\{1,2,3\}&\leftrightarrow&123\\ \varnothing\subsetneq\{1\}\subsetneq\{1,3\}\subsetneq\{1,2,3\}&\leftrightarrow&132\\ \varnothing\subsetneq\{2\}\subsetneq\{1,2\}\subsetneq\{1,2,3\}&\leftrightarrow&213\\ \varnothing\subsetneq\{2\}\subsetneq\{2,3\}\subsetneq\{1,2,3\}&\leftrightarrow&231\\ \varnothing\subsetneq\{3\}\subsetneq\{1,3\}\subsetneq\{1,2,3\}&\leftrightarrow&312\\ \varnothing\subsetneq\{3\}\subsetneq\{2,3\}\subsetneq\{1,2,3\}&\leftrightarrow&321\\ \end{matrix}$$

-
It was built by adding an element to each subsequent set. – Gbean Sep 20 '11 at 3:48
@Gbean: Yes, but in what order? First 2, then 3, then 1. So how about a permutation that, somehow, deals with 2 "first", 3 "next", and 1 "last"? – Arturo Magidin Sep 20 '11 at 3:55
I'm not sure I'm following. – Gbean Sep 20 '11 at 9:42
@Gbean: Permutations are related to "ordering" things; you count "in how many ways can I order 3 elements" with "permutations". Each ordering of 3 elements give you a permutation: for example, the order 123 corresponds to sending 1 to 1, 2 to 2, and 3 to 3. The ordering 312 corresponds to sending 1 to 3, 2 to 1, 3 to 2. Etc. Here, the tower is built up by first adding 2, then adding 3, and finally adding 1. So it makes sense to think of it as 231, which in turn corresponds to the permutation that sends 1 to 2, 2 to 3, and 3 to 1. – Arturo Magidin Sep 20 '11 at 13:42