eng
episciences.org
Discrete Mathematics & Theoretical Computer Science
1365-8050
2022-05-24
vol. 24, no. 1
Combinatorics
10.46298/dmtcs.7163
7163
journal article
Down-step statistics in generalized Dyck paths
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.
https://dmtcs.episciences.org/7163/pdf
Mathematics - Combinatorics
Computer Science - Discrete Mathematics
05A15 (Primary) 05A19, 05A05 (Secondary)