The number of permutations with a given number of sequences

2006/10/15 by Kollar, Marcus
#05A15 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.math/0610462

Abstract

P(n,s) denotes the number of permutations of 1,2,...n that have exactly s sequences. Canfield and Wilf [math.CO/0609704] recently showed that P(n,s) can be written as a sum of s polynomials in n. We determine these polynomials explicitly and also obtain explicit expressions for P(n,s) and its fixed-s generating function u_s(x).

Related

• Restricted set of patterns, continued fractions, and Chebyshev polynomials
• Counting permutations by their runs up and down
• Restricted permutations and Chebyshev polynomials
• The enumeration of simple permutations
• A note on the paper arXiv:2207.13335