430 Combinatorics of Permutations, Second Edition
obtained from T (p) by omitting its labels. As there are C
n
such trees,
we get that B has C
n
=
2n
n
/(n +1)elements.
23. We have seen in Exercise 21 that going through a stack can effect an n-
permutationinatmostC
n
ways, so an n-permutation can have at most
C
n
preimages. On the other hand, the identity permutation does have
C
n
preimages, namely all the 231-avoiding permutations. We claim this
is the only permutation with that property.
To see that no other n-permutation can have C
n
preimages, we apply
induction on n.Forn ≤ 3, the statement is clearly true. Now let us
assume the statement is true for all positive integers less than n.If
s(q)=p,andq = LnR,thenwehavep = s(L)s(R)n. Now keep n fixed
in q, in positio ...