کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647626 1342363 2013 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A reciprocity method for computing generating functions over the set of permutations with no consecutive occurrence of a permutation pattern
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A reciprocity method for computing generating functions over the set of permutations with no consecutive occurrence of a permutation pattern
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 313, Issue 23, 6 December 2013, Pages 2712-2729
نویسندگان
, ,