Journal of Combinatorics

Volume 14 (2023)

Number 3

On a conjecture of Lin and Kim concerning a refinement of Schröder numbers

Pages: 305 – 338

DOI: https://dx.doi.org/10.4310/JOC.2023.v14.n3.a2

Authors

Toufik Mansour (Department of Mathematics, University of Haifa, Israel)

Mark Shattuck (Department of Mathematics, University of Tennessee, Knoxville, Tenn., U.S.A.)

Abstract

In this paper, we compute the distribution of the first letter statistic on nine avoidance classes of permutations corresponding to two pairs of patterns of length four. In particular, we show that the distribution is the same for each class and is given by the entries of a new Schröder number triangle. This answers in the affirmative a recent conjecture of Lin and Kim. We employ a variety of techniques to prove our results, including generating trees, direct bijections and the kernel method. For the latter, we make use of in a creative way what we are trying to show to aid in solving a system of functional equations satisfied by the associated generating functions in three cases.

Keywords

pattern avoidance, combinatorial statistic, kernel method

2010 Mathematics Subject Classification

Primary 05A15. Secondary 05A05.

Received 24 July 2021

Published 28 December 2022