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

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\le k\le n$, $C_{n,k}$ is also seen to enumerate the number of 123-avoiding permutations with $n$ being in the $k$th position. Two interesting discrete probability distributions, related obliquely to the Poisson and geometric random variables, are derived as a result.

10 pages

References in corpus (2)

• Counting permutations with no long monotone subsequence via generating trees and the kernel method
• A simple combinatorial proof of Shapiro's Catalan convolution

Cited by in corpus (1)

• Telescoping Sums, Permutations, and First Occurrence Distributions