Counting 3stacksortable permutations Abstract   We prove a xe2x80x9cdecomposition lemmaxe2x80x9d that allows us to count preimages of certain sets of permutations under Westu0027s stacksorting map s. As a first application, we give a new proof of Zeilbergeru0027s formula for the number      W    2    (  n  )    of 2stacksortable permutations in      S    n     . Our proof generalizes, allowing us to find an algebraic equation satisfied by the generating function that counts 2stacksortable permutations according to length, number of descents, and number of peaks. This is also the first proof of this formula that generalizes to the setting of 3stacksortable permutations. Indeed, the same method allows us to obtain a recurrence relation for      W    3    (  n  )   , the number of 3stacksortable permutations in      S    n     . Hence, we obtain the first polynomialtime algorithm for computing these numbers. We compute      W    3    (  n  )    for    n  xe2x89xa4  174   , vastly extending the 13 terms of this sequence that were known before. We also prove the first nontrivial lower bound for     lim   n  xe2x86x92  xe2x88x9e    xe2x81xa1    W    3      (  n  )    1    n     , showing that it is at least 8.659702. Invoking a result of Kremer, we also prove that     lim   n  xe2x86x92  xe2x88x9e    xe2x81xa1    W    t      (  n  )    1    n    xe2x89xa5    (    t      1  )    2      for all    t  xe2x89xa5  1   , which we use to improve a result of Smith concerning a variant of the stacksorting procedure. Our computations allow us to disprove a conjecture of Bona, although we do not yet know for sure which one.  In fact, we can refine our methods to obtain a recurrence for      W    3    (  n  ,  k  ,  p  )   , the number of 3stacksortable permutations in      S    n      with k descents and p peaks. This allows us to gain a large amount of evidence supporting a realrootedness conjecture of Bona. Using part of the theory of valid hook configurations, we give a new proof of a xcexb3nonnegativity result of Branden, which in turn implies an older result of Bona. We then answer a question of the current author by producing a set    A  xe2x8ax86    S    11      such that      xe2x88x91    xcfx83  xe2x88x88    s    xe2x88x92  1    (  A  )      x    des  (  xcfx83  )      has nonreal roots. We interpret this as partial evidence against the same realrootedness conjecture of Bona that we found evidence supporting. Examining the parities of the numbers      W    3    (  n  )   , we obtain strong evidence against yet another conjecture of Bona. We end with some conjectures of our own.

Subsequence containment by involutions Inspired by work of McKay, Morse, and Wilf, we give an exact count of the involutions in cal S_n which contain a given permutation tauincal S_k as a subsequence; this number depends on the patterns of the first j values of tau for 1leq jleq k. We then use this to define a partition of cal S_k, analogous to Wilfclasses in the study of pattern avoidance, and examine properties of this equivalence.  In the process, we show that a permutation tau_1ldotstau_k is layered iff, for 1leq jleq k, the pattern of tau_1ldotstau_j is an involution.  We also obtain a result of Sagan and Stanley counting the standard Young tableaux of size n which contain a fixed tableau of size k as a subtableau.