On Enumeration of Families of Genus Zero Permutations

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

Research output: Contribution to journalArticle

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 languageEnglish
Pages (from-to)1337-1360
Number of pages24
JournalGraphs and Combinatorics
Volume35
Issue number6
DOIs
Publication statusPublished - 2019 Nov 1
Externally publishedYes

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

Fingerprint Dive into the research topics of 'On Enumeration of Families of Genus Zero Permutations'. Together they form a unique fingerprint.

  • Cite this