Permutation patterns, ordered trees and continued fractions

Abstract

We enumerate permutations which have exactly r 123-patterns and s 132-patterns where r+s ≤ 2. We also give a new bijection between the ordered trees on n+1 vertices and 123-avoiding permutations of length n. We define the weight of ordered trees so that the bijection becomes weight-preserving, and find the generating function, in the form of a continued fraction, of 123-avoiding permutations of length n that have exactly r 132-patterns.