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 pathsArticle

Authors: Andrei Asinowski ORCID; 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://doi.org/10.46298/dmtcs.7163
    Source: arXiv.org:2007.15562
    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)
    Licence: arXiv.org - Non-exclusive license to distribute
    Funding:
      Source : OpenAIRE Graph
    • Modeling–Analysis–Optimization of discrete, continuous, and stochastic systems; Code: DOC 78
    • Analytic Combinatorics: Digits, Automata and Trees; Code: P 28466
    • Generic Rectangulations: Enumerative and Structural Aspects; Code: P 32731

    Classifications

    Mathematics Subject Classification 20201
    Sources:
    • [1] zbMATH Open.

    Share and export

    Consultation statistics

    This page has been seen 1295 times.
    This article's PDF has been downloaded 1399 times.