Andrei Asinowski ; Benjamin Hackl ; Sarah J. Selkirk - Down-step statistics in generalized Dyck paths

dmtcs:7163 - Discrete Mathematics & Theoretical Computer Science, May 24, 2022, vol. 24, no. 1 - https://doi.org/10.46298/dmtcs.7163
Down-step statistics in generalized Dyck paths

Authors: Andrei Asinowski ; Benjamin Hackl ; Sarah J. Selkirk

The number of down-steps between pairs of up-steps in $k_t$-Dyck paths, a generalization of Dyck paths consisting of steps $\{(1, k), (1, -1)\}$ such that the path stays (weakly) above the line $y=-t$, is studied. Results are proved bijectively and by means of generating functions, and lead to several interesting identities as well as links to other combinatorial structures. In particular, there is a connection between $k_t$-Dyck paths and perforation patterns for punctured convolutional codes (binary matrices) used in coding theory. Surprisingly, upon restriction to usual Dyck paths this yields a new combinatorial interpretation of Catalan numbers.

Volume: vol. 24, no. 1
Section: Combinatorics
Published on: May 24, 2022
Accepted on: April 21, 2022
Submitted on: February 8, 2021
Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics,05A15 (Primary) 05A19, 05A05 (Secondary)