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.

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

share|improve this question
2  
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
2  
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
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
It was built by adding an element to each subsequent set. –  Gbean Sep 20 '11 at 3:48
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"? –  Arturo Magidin Sep 20 '11 at 3:55
    
I'm not sure I'm following. –  Gbean Sep 20 '11 at 9:42
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. –  Arturo Magidin Sep 20 '11 at 13:42
add comment

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.