Discrete Mathematics & Theoretical Computer Science |

- 1 University of Haifa [Haifa]

Let asc and desc denote respectively the statistics recording the number of ascents or descents in a sequence having non-negative integer entries. In a recent paper by Andrews and Chern, it was shown that the distribution of asc on the inversion sequence avoidance class $I_n(\geq,\neq,>)$ is the same as that of $n-1-\text{asc}$ on the class $I_n(>,\neq,\geq)$, which confirmed an earlier conjecture of Lin. In this paper, we consider some further enumerative aspects related to this equivalence and, as a consequence, provide an alternative proof of the conjecture. In particular, we find recurrence relations for the joint distribution on $I_n(\geq,\neq,>)$ of asc and desc along with two other parameters, and do the same for $n-1-\text{asc}$ and desc on $I_n(>,\neq,\geq)$. By employing a functional equation approach together with the kernel method, we are able to compute explicitly the generating function for both of the aforementioned joint distributions, which extends (and provides a new proof of) the recent result $|I_n(\geq,\neq,>)|=|I_n(>,\neq,\geq)|$. In both cases, an algorithm is formulated for computing the generating function of the asc distribution on members of each respective class having a fixed number of descents.

Source: HAL:hal-03295362v3

Volume: vol. 24, no. 1

Section: Combinatorics

Published on: February 7, 2022

Accepted on: January 19, 2022

Submitted on: August 3, 2021

Keywords: 65Q30 pattern avoidance,combinatorial statistic,July 22,2021. 2010 Mathematics Subject Classification. 05A15,05A05,65Q20,kernel method,inversion sequence,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],[MATH.MATH-MP]Mathematics [math]/Mathematical Physics [math-ph]

This page has been seen 1112 times.

This article's PDF has been downloaded 1034 times.