Trees, parking functions and factorizations of full cycles

DOI10.1016/J.EJC.2020.103257MaRDI QIDQ2225449zbMATH OpenOpenAlexWikidataFDO

Authors J. Irving, Amarpreet Rattan

Publication date 8 February 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.10123

zbMATH Keywords

Haglund's bounce statistic on parking functionsinversion enumeratorlabelled treesStanley's function

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Trees (05C05) Enumeration in graph theory (05C30) Paths and cycles (05C38) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: Parking functions of length $n$ are well known to be in correspondence with both labelled trees on $n+1$ vertices and factorizations of the full cycle $sigm{a}_n=(0,1,cdots,n)$ into $n$ transpositions. In fact, these correspondences can be refined: Kreweras equated the area enumerator of parking functions with the inversion enumerator of labelled trees, while an elegant bijection of Stanley maps the area of parking functions to a natural statistic on factorizations of $sigm{a}_n$. We extend these relationships in two principal ways. First, we introduce a bivariate refinement of the inversion enumerator of trees and show that it matches a similarly refined enumerator for factorizations. Secondly, we characterize all full cycles $sigma$ such that Stanley's function remains a bijection when the canonical cycle $sigm{a}_n$ is replaced by $sigma$. We also exhibit a connection between our refined inversion enumerator and Haglund's bounce statistic on parking functions.

Recommendations

• Parking functions, tree depth and factorizations of the full cycle into transpositions
• Parking functions and labeled trees
• Parking functions and tree inversions revisited
• G-parking functions and tree inversions
• Generalized parking functions, tree inversions, and multicolored graphs

Cites work

• A solution to a problem of Dénes: A bijection between trees and factorizations of cyclic permutations
• An Occupancy Discipline and Applications
• Depth-first search as a combinatorial correspondence
• Enumerative applications of a decomposition for graphs and digraphs
• Graphs on surfaces and their applications. Appendix by Don B. Zagier
• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 3149991 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• Jucys-Murphy elements and unitary matrix integrals
• Mahonian statistics on labeled forests
• On external activity and inversions in trees
• On maximal chains in the non-crossing partition lattice
• On the analysis of linear probing hashing
• Parking functions
• Parking functions and noncrossing partitions
• Parking functions of types A and B
• Parking functions, tree depth and factorizations of the full cycle into transpositions
• q-hook length formulas for forests
• Some factorisations counted by Catalan numbers
• Sorting index and Mahonian-Stirling pairs for labeled forests
• The q,t-Catalan numbers and the space of diagonal harmonics. With an appendix on the combinatorics of Macdonald polynomials
• The inversion enumerator for labeled trees
• Transitive factorizations of permutations and geometry
• Tree-like properties of cycle factorizations
• Two element lattice permutation numbers and their \(q\)-generalization
• Une famille de polynômes ayant plusieurs propriétés enumeratives

Cited in

(17)

• Parking functions, valet functions and priority queues
• Generalized tree inversions and \(k\)-parking functions
• Transitive cycle factorizations and prime parking functions
• G-parking functions and tree inversions
• Symmetries in trees and parking functions
• An area-depth symmetric \(q, t\)-Catalan polynomial
• k-indivisible noncrossing partitions
• Parking functions on directed graphs and some directed trees
• Factorizations of cycles and multi-noded rooted trees
• Labelled trees and factorizations of a cycle into transpositions
• Permutation factorizations and prime parking functions
• Parking functions and tree inversions revisited
• Parking functions, tree depth and factorizations of the full cycle into transpositions
• \(k\)-factorizations of the full cycle and generalized Mahonian statistics on \(k\)-forests
• Parking functions and labeled trees
• Random monotone factorisations of the cycle and their lamination process
• G-parking functions, acyclic orientations and spanning trees

This page was built for publication: Trees, parking functions and factorizations of full cycles

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