Geodesic
Counting permutations with no long monotone subsequence via generating trees and the kernel method
Journal of Algebraic Combinatorics, Tome 33 (2011) no. 4, pp. 571-608.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: We recover Gessel's determinantal formula for the generating function of permutations with no ascending subsequence of length $m+1$. The starting point of our proof is the recursive construction of these permutations by insertion of the largest entry. This construction is of course extremely simple. The cost of this simplicity is that we need to take into account in the enumeration $m - 1$ additional parameters-namely, the positions of the leftmost increasing subsequences of length $i$, for $i=2,\cdots , m$. This yields for the generating function a functional equation with $m - 1$ "catalytic" variables, and the heart of the paper is the solution of this equation. We perform a similar task for involutions with no descending subsequence of length $m+1$, constructed recursively by adding a cycle containing the largest entry. We refine this result by keeping track of the number of fixed points.
Keywords: keywords permutations, ascending subsequences, generating functions, generating trees 
@article{JAC_2011__33_4_a1,
     author = {Bousquet-M\'elou, Mireille},
     title = {Counting permutations with no long monotone subsequence via generating trees and the kernel method},
     journal = {Journal of Algebraic Combinatorics},
     pages = {571--608},
     publisher = {mathdoc},
     volume = {33},
     number = {4},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JAC_2011__33_4_a1/}
}
TY  - JOUR
AU  - Bousquet-Mélou, Mireille
TI  - Counting permutations with no long monotone subsequence via generating trees and the kernel method
JO  - Journal of Algebraic Combinatorics
PY  - 2011
SP  - 571
EP  - 608
VL  - 33
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JAC_2011__33_4_a1/
LA  - en
ID  - JAC_2011__33_4_a1
ER  - 
%0 Journal Article
%A Bousquet-Mélou, Mireille
%T Counting permutations with no long monotone subsequence via generating trees and the kernel method
%J Journal of Algebraic Combinatorics
%D 2011
%P 571-608
%V 33
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JAC_2011__33_4_a1/
%G en
%F JAC_2011__33_4_a1
Bousquet-Mélou, Mireille. Counting permutations with no long monotone subsequence via generating trees and the kernel method. Journal of Algebraic Combinatorics, Tome 33 (2011) no. 4, pp. 571-608. http://geodesic.mathdoc.fr/item/JAC_2011__33_4_a1/