Article ID Journal Published Year Pages File Type
4647626 Discrete Mathematics 2013 18 Pages PDF
Abstract
In this paper, we introduce a new method for computing generating functions with respect to the number of descents and left-to-right minima over the set of permutations which have no consecutive occurrence of τ where τ starts with 1. In particular, we study the generating function ∑n≥0tnn!∑σ∈NMn(1324…p)xLRmin(σ)y1+des(σ) where p≥4, NMn(1324…p) is the set of permutations σ in the symmetric group Sn which has no consecutive occurrences of 1324…p, des(σ) is the number of descents of σ and LRmin(σ) is the number of left-to-right minima of σ. We show that for any p≥4, this generating function is of the form (1U(t,y))x where U(t,y)=∑n≥0Un(y)tnn! and the coefficients Un(y) satisfy some simple recursions depending on p. As an application of our results, we compute explicit generating functions for the number of permutations of Sn that have no consecutive occurrences of the pattern 1324…p and have exactly k descents for k=1,2.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,