10.46298/dmtcs.7163
https://dmtcs.episciences.org/7163
Asinowski, Andrei
Andrei
Asinowski
Hackl, Benjamin
Benjamin
Hackl
Selkirk, Sarah J.
Sarah J.
Selkirk
Austrian Science Fund (FWF)
P 28466
Analytic Combinatorics: Digits, Automata and Trees
Down-step statistics in generalized Dyck paths
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.
episciences.org
Mathematics - Combinatorics
Computer Science - Discrete Mathematics
05A15 (Primary) 05A19, 05A05 (Secondary)
arXiv.org - Non-exclusive license to distribute
2022-04-21
2022-05-24
2022-05-24
eng
journal article
arXiv:2007.15562
10.48550/arXiv.2007.15562
1365-8050
https://dmtcs.episciences.org/7163/pdf
VoR
application/pdf
Discrete Mathematics & Theoretical Computer Science
vol. 24, no. 1
Combinatorics
Researchers
Students