1
$\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
    You're not reading the description of what a tower is properly.2011-09-20
  • 0
    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.2011-09-20
  • 2
    It’s defined in the statement of the problem: it’s a sequence of sets satisfying certain constraints involving inclusions and cardinalities.2011-09-20

1 Answers 1

3

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

  • 0
    It was built by adding an element to each subsequent set.2011-09-20
  • 3
    @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"?2011-09-20
  • 0
    I'm not sure I'm following.2011-09-20
  • 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