The Road Grid Arrangement With The Prohibitions

Permutations with forbidden patterns have been extensively studied over the last decade. Several classical sequences of numbers in Combinatorics arise in the problem of enumerating permutations with forbidden patterns.The first explicit enumeration of S_n(321) seems to be due to Hammersley. Knuth first proved that S_n(231) is enumerated by Catalan numbers. Gire first discovered that S_n(321,31|-42) and S_n(231,41|-32) are enumerated by the n-th Motzkin numbers. Gire and West found that three classes of permutations with forbidden patterns are enumerated by the Schroder numbers. Stanley conjectured that for ten pairs of patterns of length 4, permutations avoiding these patterns are all enumerated by the Schroder numbers. Later Kremer proved it.It is well known that these numbers enumerate certain lattice paths, and it is more easy and intuitive when some statistics on permutations with forbidden patterns are reflected on lattices paths. So it is a revealing problem to find the bijections between permutations with forbidden patterns and the corresponding lattice paths.There are many efforts on these objects. The most usual method is ECO methodology which gives the bijection by showing that they have the same generating trees. While we prefer some more intuitive and directed bijections.In this thesis, we will use a new method, called canonical reduced decompositions, to characterize permutations with forbidden patterns. Then by labelling and decomposing the corresponding lattice paths, we give the bijections between them. The sketch of the thesis is as follows: We start the thesis with some definitions and notations in Chapter 1. We give the bijections between S_n(321), S₂₃₁ and Dyck paths respectively, and further obtain a bijection between D_n(321) and Fine paths in Chapter 2. We construct the bijections between S_n(321,31|-42), S_n(231,41|-32) and Motzkin paths in Chapter 3. In Chapter 4, we first define a new kind of lattice paths — Riordan paths, and prove that it is enumerated by Riordan numbers, then we show a bijection between D_n(321,31|-42) and Riordan paths. In Chapter 5, we show the bijections between S_n(1243,2143), S_n(4231,4132) and Schro|¨der Paths. Furthermore, for the above classes of permutations, we also study some of their statisticsrespectively. Finally, by restricting the wave steps of 2-Motzkin path, we provide a kind of "discrete continuity" between the Motzkin and the Catalan numbers, which answers a problem by Barcucci, Del Lungo, Pergola and Pinzani.