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 Cn,k. For 1 ? k ? n, Cn,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.
展开▼
