The Location of the First Ascent in a 123-Avoiding Permutation

2014/01/13 by Samuel Connolly, Connolly, Samuel, Zachary Gabor +3
Mathematics · #05A05 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A05

paper · pdf · doi:10.48550/arxiv.1401.2691

10 pages

arxiv created 2014/01/13 · arxiv updated 2014/01/14

Abstract

It is natural to ask, given a permutation with no three-term ascending subsequence, at what index the first ascent occurs. We shall show, using both a recursion and a bijection, that the number of 123-avoiding permutations at which the first ascent occurs at positions k,k+1 is given by the k-fold Catalan convolution C_n,k. For 1≤ k≤ n, C_n,k is also seen to enumerate the number of 123-avoiding permutations with n being in the kth position. Two interesting discrete probability distributions, related obliquely to the Poisson and geometric random variables, are derived as a result.

Related

• Ascent sequences and the binomial convolution of Catalan numbers
• The descent statistic over 123-avoiding permutations
• Two permutation classes enumerated by the central binomial coefficients
• Another bijection for 021-avoiding ascent sequences
• A proof of Catalan's Convolution formula