3
$\begingroup$

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!$

  • 2
    It’s defined in the state$m$ent of the proble$m$: it’s a sequence of sets satisfying certain constraints involving inclusions and cardinalities.2011-09-20

1 Answers 1

4

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

  • 1
    @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.2011-09-20