An explicit formula for the number of permutations with a given number of alternating runs

DOI10.1016/J.JCTA.2012.05.005zbMATH Open1246.05011arXiv1110.6779OpenAlexW2091870483MaRDI QIDQ444901FDOQ444901

Authors: Shi-Mei Ma 

Publication date: 24 August 2012

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: Let $R(n,k)$ denote the number of permutations of $1,2,\mathrm{...},n$ with $k$ alternating runs. In this note we present an explicit formula for the numbers $R(n,k)$.

Full work available at URL: https://arxiv.org/abs/1110.6779

zbMATH Keywords

permutationsEulerian polynomialsalternating runsderivative polynomials

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Symmetric groups (20B30)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Derivative polynomials and enumeration of permutations by number of interior and left peaks
• Longest alternating subsequences of permutations
• A combinatorial proof of the log-concavity of the numbers of permutations with \(k\) runs
• Functions with derivatives given by polynomials in the function itself or a related function
• Counting permutations by their alternating runs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Derivative Polynomials for Tangent and Secant
• Derivative polynomials and closed-form higher derivative formulae
• Tangent numbers and operators
• Combinatorial extreme value distributions

Cited In (16)

• The peak statistics on simsun permutations
• Several variants of the Dumont differential system and permutation statistics
• Enumeration of permutations by number of alternating runs
• An asymptotic distribution theory for Eulerian recurrences with applications
• Counting permutations by simsun successions
• On \(\gamma\)-vectors and the derivatives of the tangent and secant functions
• Generating functions of permutations with respect to their alternating runs
• Run distribution over flattened partitions
• Enumeration of type \(D\) permutations with alternating runs
• Subalgebras of Solomon's descent algebra based on alternating runs
• The \(1 / k\)-Eulerian polynomials and \(k\)-Stirling permutations
• Counting signed permutations by their alternating runs
• Enumeration of permutations by number of alternating descents
• David-Barton type identities and alternating run polynomials
• On the alternating runs polynomial in type B and type D Coxeter groups
• Context-free grammars, generating functions and combinatorial arrays

Uses Software

• OEIS

This page was built for publication: An explicit formula for the number of permutations with a given number of alternating runs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q444901)