Abstrakt. Vi uppvisar en biject mellan 132-undvikande permutationer och Dyck stigar. Med hjälp av denna bijective, visas det att alla nyligen upptäckta resultat på generera funktioner för 132-undvikande permutationer med ett givet antal förekomster av mönstret 12... k följa direkt från gamla resultat på uppräkning av Motzkin vägar, bland vilka är ett fortsatt bråk resultat på grund av Flajolet. Som bonus använder vi dessa observationer för att härleda ytterligare resultat och en exakt asymptotisk uppskattning för antalet 132-undvikande permutationer av {1, 2,..., n} med exakt r förekomster av mönstret 12... k. För det andra uppvisar vi en bistick mellan 123-undvikande permutationer och Dyck vägar. I kombination med ett resultat av Roblet och Viennot kan vi uttrycka generatorfunktionen för 123-undvikande permutationer med ett givet antal förekomster av mönstret (k − 1)(k − 2). ... 1k i form av en fortsatt fraktion och för att få ytterligare resultat för dessa permutationer.
Krattenthaler REF (och, självständigt, E. Deutsch) upptäckte nyligen eleganta bijetter mellan Dyck banor och -undvikande permutationer.
Permutations with restricted patterns and Dyck paths
{'venue': 'Adv. Appl. Math', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}