The study of permutation patterns began with Knuth’s analysis of a certain “stack-sorting algorithm” in 1968. In his 1990 PhD. thesis, West investigated a deterministic variant of Knuth’s algorithm, which we can view as a function s that defines a dynamical system on the set of permutations. He defined the fertility of a permutation to be the number of preimages of that permutation under s. We will describe a colorful method for computing the fertility of any permutation, answering a question of Bousquet-Mélou.

Applications of this method allow us to reprove and generalize several known theorems and improve the best known upper bound for the number of so-called “t-stack-sortable” permutations of length n when t=3 and when t=4. The method also allows us to connect the stack-sorting map with free probability theory, set partitions, acyclic orientations of graphs, lattice paths, and several well-studied sequences. Finally, we will consider two operators on words that extend the stack-sorting map.