کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647587 | 1632426 | 2014 | 13 صفحه PDF | دانلود رایگان |
An ascent sequence is a sequence consisting of non-negative integers in which the size of each letter is restricted by the number of ascents preceding it in the sequence. Ascent sequences have recently been shown to be related to (2+2)(2+2)-free posets and a variety of other combinatorial structures. In this paper, we prove some recent conjectures of Duncan and Steingrímsson concerning pattern avoidance for ascent sequences. Given a pattern ττ, let Sτ(n)Sτ(n) denote the set of ascent sequences of length nn avoiding ττ. Here, we show that the joint distribution of the statistic pair (asc,zeros) on S0012(n)S0012(n) is the same as (asc,RLmax) on the set of 132132-avoiding permutations of length nn. In particular, the ascent statistic on S0012(n)S0012(n) has the Narayana distribution. We also enumerate Sτ(n)Sτ(n) when τ=1012τ=1012 or τ=0123τ=0123 and confirm the conjectured formulas in these cases. We combine combinatorial and algebraic techniques to prove our results, in two cases, making use of the kernel method. Finally, we discuss the case of avoiding 210 and determine two related recurrences.
Journal: Discrete Mathematics - Volumes 315–316, 6 February 2014, Pages 29–41