Tags: #theorem

Statement

Let $\sigma \in S_3$ be a pattern. Then, the number of $\sigma$-avoiding permutations in $S_n$ is $C_n$ (Catalan numbers)

Proof

If a permutation is

• 2, 3, 1-avoidant, then it is stack-sortable and the number of such permutations is Catalan.
  • The number of permutations that are 1,3,2-avoidant is also the same (as we just reverse all the permutations)
• 3,2,1-avoidant, then it is 2-queue sortable and we can use the fact that the number of permutations that are 2-queue sortable is catalan.
  • Same as the above comment but with 1,2,3
• I lowkey missed the point about what happens if you have 2,1,3 - maybe there is some kind of symmetry argument that I missed?