Permutations with restricted patterns and Dyck paths
| dc.creator | Krattenthaler, Christian | |
| dc.date | 2000-02-24 | |
| dc.date.accessioned | 2026-07-07T04:34:02Z | |
| dc.date.available | 2026-07-07T04:34:02Z | |
| dc.description | We exhibit a bijection between 132-avoiding permutations and Dyck paths. Using this bijection, it is shown that all the recently discovered results on generating functions for 132-avoiding permutations with a given number of occurrences of the pattern $12... k$ follow directly from old results on the enumeration of Motzkin paths, among which is a continued fraction result due to Flajolet. As a bonus, we use these observations to derive further results and a precise asymptotic estimate for the number of 132-avoiding permutations of $\{1,2,...,n\}$ with exactly $r$ occurrences of the pattern $12... k$. Second, we exhibit a bijection between 123-avoiding permutations and Dyck paths. When combined with a result of Roblet and Viennot, this bijection allows us to express the generating function for 123-avoiding permutations with a given number of occurrences of the pattern $(k-1)(k-2)... 1k$ in form of a continued fraction and to derive further results for these permutations. | |
| dc.description | 17 pages, AmS-TeX | |
| dc.identifier | https://arxiv.org/abs/math/0002200 | |
| dc.identifier | http://arxiv.org/abs/math/0002200 | |
| dc.identifier | Adv. Appl. Math. 27 (2001), 510-530 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/58750 | |
| dc.subject | Combinatorics | |
| dc.subject | 05A05 (Primary) 05A15 05A16 (Secondary) | |
| dc.title | Permutations with restricted patterns and Dyck paths | |
| dc.type | text |