2010/08/13 by David Callan, Callan, David · 1 citation
Mathematics · Engineering · Computer Science · #Advanced Combinatorial Mathematics #graph theory and CDMA systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1008.2375
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.