Counting partitions of a fixed genus

MaRDI QIDQ1627201zbMATH OpenFDO

Authors Robert Cori, Gabor Hetyei

Publication date 22 November 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.09992, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p26

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

genus of a hypermapnoncrossing partitionsset partitions

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30)

Abstract: We show that, for any fixed genus $g$, the ordinary generating function for the genus $g$ partitions of an $n$-element set into $k$ blocks is algebraic. The proof involves showing that each such partition may be reduced in a unique way to a primitive partition and that the number of primitive partitions of a given genus is finite. We illustrate our method by finding the generating function for genus $2$ partitions, after identifying all genus $2$ primitive partitions, using a computer-assisted search.

Review text

Summary: We show that, for any fixed genus \(g\), the ordinary generating function for the genus \(g\) partitions of an \(n\)-element set into \(k\) blocks is algebraic. The proof involves showing that each such partition may be reduced in a unique way to a primitive partition and that the number of primitive partitions of a given genus is finite. We illustrate our method by finding the generating function for genus \(2\) partitions, after identifying all genus \(2\) primitive partitions, using a computer-assisted search.

Recommendations

• Counting genus one partitions and permutations
• How to count genus one partitions
• Exact generating functions for the number of partitions into distinct parts
• Counting homomorphisms and partition functions
• scientific article; zbMATH DE number 3091935
• Counting partitions of graphs
• scientific article; zbMATH DE number 502837
• scientific article; zbMATH DE number 819114
• Partitionings of a genus of quadratic forms
• Number theoretic properties of generating functions related to Dyson's rank for partitions into distinct parts

Cites work

• A Character Theoretic Approach to Embeddings of Rooted Maps in an Orientable Surface of Given Genus
• A type-B associahedron.
• Analytic combinatorics
• Character Theory and Rooted Maps in an Orientable Surface of Given Genus: Face-Colored Maps
• Counting genus one partitions and permutations
• Counting rooted maps by genus. I
• Delannoy orthants of Legendre polytopes
• Factoring \(n\)-cycles and counting maps of given genus
• scientific article; zbMATH DE number 3489159 (Why is no real title available?)
• scientific article; zbMATH DE number 3298598 (Why is no real title available?)
• Maps in Locally Orientable Surfaces, the Double Coset Algebra, and Zonal Polynomials
• On the number of convex polyominoes.
• On Tutte's chromatic invariant
• Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
• The On-Line Encyclopedia of Integer Sequences
• The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees

Cited in

(7)

• Counting non-crossing permutations on surfaces of any genus
• On enumeration of families of genus zero permutations
• Counting genus one partitions and permutations
• How to count genus one partitions
• Counting partitions by genus: a compendium of results
• Counting partitions by genus. I. Genus 0 to 2
• Genus permutations and genus partitions

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Counting partitions of a fixed genus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1627201)