Counting permutations with no long monotone subsequence via generating trees and the kernel method |
| |
Authors: | Mireille Bousquet-Mélou |
| |
Institution: | (1) Department of Physics and Computer Science, Wilfrid Laurier University, Waterloo, Ontario, N2L 3C5, Canada;(2) School of Mathematics, University of Southampton, Southampton, SO17 1BJ, England |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|