A bijection to count (1-23-4)-avoiding permutations
A permutation is (1-23-4)-avoiding if it contains no four entries,
increasing left to right, with the middle two adjacent in the
permutation. Here we give a 2-variable recurrence for the number of
such permutations, improving on the previously known 4-variable recurrence.
At the heart of the proof is a bijection from (1-23-4)-avoiding
permutations to increasing ordered trees whose leaves, taken in
preorder, are also increasing.
