Symmetries in trees and parking functions
type: Item
instance of: scholarly article
title: Symmetries in trees and parking functions
zbMATH Open document ID: 1010.05021
DOI: 10.1016/S0012-365X(02)00344-8
author: Louis H. Kalikow
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: The author gives two new proofs of the following fact first discovered by Gessel: in the set of rooted labeled trees of \(n+1\) vertices rooted at the smallest vertex, the number of trees with \(a\) descents and \(b+1\) leaves equals the number of trees with \(b\) descents and \(a+1\) leaves (a descent is a vertex whose label is greater than at least one of its children labels). His approach uses decompositions of trees and leads to a generalization of a well-known bijection from \(\{1,\dots, n\}\) to increasing trees (i.e. trees with no descents) and to a generalization found by Knuth involving intransitive trees. One of these decompositions is related to symmetry in parking functions. The received results are generalized to binary trees.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05A15
zbMATH DE Number: 1838964
zbMATH Keywords: leaves
zbMATH Keywords: descent
zbMATH Keywords: decompositions
zbMATH Keywords: binary trees
MaRDI profile type: Publication
Recommended article: A symmetry on parking functions via Dyck paths
Recommended article: Parking functions and tree inversions revisited
Recommended article: Symmetries and Ramsey properties of trees
Recommended article: Trees, parking functions and factorizations of full cycles
Recommended article: Parking functions on oriented trees
Recommended article: Q4400939
Recommended article: \(G\)-parking functions and tree inversions
Recommended article: The symmetry number problem for trees
Recommended article: Parking function varieties for combinatorial tree models
Recommended article: Generalized tree inversions and \(k\)-parking functions
description: scientific article; zbMATH DE number 1838964