On Enumeration of Families of Genus Zero Permutations

Sen Peng Eu; Tung Shan Fu; Yeh Jong Pan; Chien Tai Ting

doi:10.1007/s00373-019-02111-5

On Enumeration of Families of Genus Zero Permutations

Sen Peng Eu, Tung Shan Fu, Yeh Jong Pan, Chien Tai Ting^*

^*Corresponding author for this work

Department of Mathematics

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

Abstract

The genus of a permutation σ of length n is the nonnegative integer g_σ given by n+ 1 - 2 g_σ= cyc(σ) + cyc(σ^{- 1}ζ_n) , where cyc(σ) is the number of cycles of σ and ζ_n is the cyclic permutation (1 , 2 , … , n). On the basis of a connection between genus zero permutations and noncrossing partitions, we enumerate the genus zero permutations with various restrictions, including André permutations, simsun permutations, and smooth permutations. Moreover, we present refined sign-balance results on genus zero permutations and their analogues restricted to connected permutations.

Original language	English
Pages (from-to)	1337-1360
Number of pages	24
Journal	Graphs and Combinatorics
Volume	35
Issue number	6
DOIs	https://doi.org/10.1007/s00373-019-02111-5
Publication status	Published - 2019 Nov 1

Keywords

André permutation
Genus zero permutation
Noncrossing partition
Sign-balance identity
Simsun permutation
Smooth permutation

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00373-019-02111-5

Cite this

@article{51a234ef5bcf47f08139dd2630b2da0c,

title = "On Enumeration of Families of Genus Zero Permutations",

abstract = "The genus of a permutation σ of length n is the nonnegative integer gσ given by n+ 1 - 2 gσ= cyc(σ) + cyc(σ- 1ζn) , where cyc(σ) is the number of cycles of σ and ζn is the cyclic permutation (1 , 2 , … , n). On the basis of a connection between genus zero permutations and noncrossing partitions, we enumerate the genus zero permutations with various restrictions, including Andr{\'e} permutations, simsun permutations, and smooth permutations. Moreover, we present refined sign-balance results on genus zero permutations and their analogues restricted to connected permutations.",

keywords = "Andr{\'e} permutation, Genus zero permutation, Noncrossing partition, Sign-balance identity, Simsun permutation, Smooth permutation",

author = "Eu, {Sen Peng} and Fu, {Tung Shan} and Pan, {Yeh Jong} and Ting, {Chien Tai}",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Japan KK, part of Springer Nature.",

year = "2019",

month = nov,

day = "1",

doi = "10.1007/s00373-019-02111-5",

language = "English",

volume = "35",

pages = "1337--1360",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "6",

}

TY - JOUR

T1 - On Enumeration of Families of Genus Zero Permutations

AU - Eu, Sen Peng

AU - Fu, Tung Shan

AU - Pan, Yeh Jong

AU - Ting, Chien Tai

PY - 2019/11/1

Y1 - 2019/11/1

N2 - The genus of a permutation σ of length n is the nonnegative integer gσ given by n+ 1 - 2 gσ= cyc(σ) + cyc(σ- 1ζn) , where cyc(σ) is the number of cycles of σ and ζn is the cyclic permutation (1 , 2 , … , n). On the basis of a connection between genus zero permutations and noncrossing partitions, we enumerate the genus zero permutations with various restrictions, including André permutations, simsun permutations, and smooth permutations. Moreover, we present refined sign-balance results on genus zero permutations and their analogues restricted to connected permutations.

AB - The genus of a permutation σ of length n is the nonnegative integer gσ given by n+ 1 - 2 gσ= cyc(σ) + cyc(σ- 1ζn) , where cyc(σ) is the number of cycles of σ and ζn is the cyclic permutation (1 , 2 , … , n). On the basis of a connection between genus zero permutations and noncrossing partitions, we enumerate the genus zero permutations with various restrictions, including André permutations, simsun permutations, and smooth permutations. Moreover, we present refined sign-balance results on genus zero permutations and their analogues restricted to connected permutations.

KW - André permutation

KW - Genus zero permutation

KW - Noncrossing partition

KW - Sign-balance identity

KW - Simsun permutation

KW - Smooth permutation

UR - http://www.scopus.com/inward/record.url?scp=85074698363&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85074698363&partnerID=8YFLogxK

U2 - 10.1007/s00373-019-02111-5

DO - 10.1007/s00373-019-02111-5

M3 - Article

AN - SCOPUS:85074698363

SN - 0911-0119

VL - 35

SP - 1337

EP - 1360

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 6

ER -

On Enumeration of Families of Genus Zero Permutations

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this