Enumeration of permutations by number of alternating runs

2011/10/23 by Shi-Mei Ma, Ma, Shi-Mei · 1 citation
Mathematics · Computer Science · #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Bayesian Methods and Mixture Models

paper · pdf · doi:10.48550/arxiv.1110.5014

Abstract

Let R(n,k) denote the number of permutations of 1,2,...,n with k alternating runs. We find a grammatical description of the numbers R(n,k) and then present several convolution formulas involving the generating function for the numbers R(n,k). Moreover, we establish a connection between alternating runs and Andre permutations.

Cited by

• Counting permutations by alternating runs via Hetyei-Reiner trees

Related

• An explicit formula for the number of permutations with a given number of alternating runs
• On the number of permutations with bounded run lengths
• Alternating runs of permutations and the central factorial numbers
• Counting permutations by alternating descents
• Enumeration of permutations by number of cyclic occurrence of peaks and valleys