Catalan–Spitzer Permutations

Richard Ehrenborg; Gábor Hetyei; Margaret Readdy

doi:10.54550/ECA2024V4S2R15

Catalan–Spitzer Permutations

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

We study two classes of permutations intimately related to the visual proof of Spitzer’s lemma and Huq’s generalization of the Chung–Feller theorem. Both classes of permutations are counted by the Fuss– Catalan numbers. The study of one class leads to a generalization of results of Flajolet from continued fractions to continuants. The study of the other class leads to the discovery of a restricted variant of the Foata–Strehl group action.

Original language	English
Article number	S2R15
Journal	Enumerative Combinatorics and Applications
Volume	4
Issue number	2
DOIs	https://doi.org/10.54550/ECA2024V4S2R15
State	Published - 2024

Bibliographical note

Publisher Copyright:
© 2024, University of Haifa Department of Mathematics. All rights reserved.

Funding

This work was partially supported by grants from the Simons Foundation (#429370 to Richard Ehrenborg, #245153 and #514648 to Gábor Hetyei, #422467 to Margaret Readdy). Margaret Readdy was also supported by NSF grant DMS-2247382.

Funders	Funder number
Simons Foundation	422467, 429370, 514648, 245153
National Science Foundation Arctic Social Science Program	2247382, DMS-2247382

Keywords

Continued fraction
Foata–Strehl group action
Fuss–Catalan number
Motzkin path
Raney number

ASJC Scopus subject areas

General Mathematics

Access to Document

10.54550/ECA2024V4S2R15

Cite this

@article{0a9e04996bb84ee38b7f4a38f1fdcfe5,

title = "Catalan–Spitzer Permutations",

abstract = "We study two classes of permutations intimately related to the visual proof of Spitzer{\textquoteright}s lemma and Huq{\textquoteright}s generalization of the Chung–Feller theorem. Both classes of permutations are counted by the Fuss– Catalan numbers. The study of one class leads to a generalization of results of Flajolet from continued fractions to continuants. The study of the other class leads to the discovery of a restricted variant of the Foata–Strehl group action.",

keywords = "Continued fraction, Foata–Strehl group action, Fuss–Catalan number, Motzkin path, Raney number",

author = "Richard Ehrenborg and G{\'a}bor Hetyei and Margaret Readdy",

year = "2024",

doi = "10.54550/ECA2024V4S2R15",

language = "English",

volume = "4",

number = "2",

}

TY - JOUR

T1 - Catalan–Spitzer Permutations

AU - Ehrenborg, Richard

AU - Hetyei, Gábor

AU - Readdy, Margaret

PY - 2024

Y1 - 2024

N2 - We study two classes of permutations intimately related to the visual proof of Spitzer’s lemma and Huq’s generalization of the Chung–Feller theorem. Both classes of permutations are counted by the Fuss– Catalan numbers. The study of one class leads to a generalization of results of Flajolet from continued fractions to continuants. The study of the other class leads to the discovery of a restricted variant of the Foata–Strehl group action.

AB - We study two classes of permutations intimately related to the visual proof of Spitzer’s lemma and Huq’s generalization of the Chung–Feller theorem. Both classes of permutations are counted by the Fuss– Catalan numbers. The study of one class leads to a generalization of results of Flajolet from continued fractions to continuants. The study of the other class leads to the discovery of a restricted variant of the Foata–Strehl group action.

KW - Continued fraction

KW - Foata–Strehl group action

KW - Fuss–Catalan number

KW - Motzkin path

KW - Raney number

UR - https://www.scopus.com/pages/publications/105038542619

UR - https://www.scopus.com/pages/publications/105038542619#tab=citedBy

U2 - 10.54550/ECA2024V4S2R15

DO - 10.54550/ECA2024V4S2R15

M3 - Article

AN - SCOPUS:105038542619

VL - 4

JO - Enumerative Combinatorics and Applications

JF - Enumerative Combinatorics and Applications

IS - 2

M1 - S2R15

ER -

Catalan–Spitzer Permutations

Abstract

Bibliographical note

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this