Mathematics – Combinatorics
Scientific paper
2010-06-02
Mathematics
Combinatorics
Scientific paper
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,...,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. In passing, we prove that the ordinary generating functions of these families of permutations can be expressed as constant terms of rational series.
No associations
LandOfFree
Counting permutations with no long monotone subsequence via generating trees and the kernel method does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Counting permutations with no long monotone subsequence via generating trees and the kernel method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting permutations with no long monotone subsequence via generating trees and the kernel method will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-512614