
Get Them All. Algorithms and Permutations. 323
THEOREM 8.18
For all fixed n and t, we have W
t
(n, k)=W
t
(n, n −1 −k).
PROOF There seems to be no trivial reason for this symmetry. Indeed,
the usual symmetries of permutation classes (reverse, complement) that turn
ascents into descents do not preserve the t-stack sortable property, even when
t = 1. In order to prove our theorem, we need to find a more subtle symmetry
that turns ascents into descents, and preserves the t-stack sortable property
for any t.
Before we can define this symmetry, we need to extend the notion of binary
plane trees that we discussed in Exercise 27 of Chapter 4 in relation to 231-
av