Bijections on rooted trees with fixed size of maximal decreasing subtrees

DOI10.1007/S00026-013-0182-9zbMATH Open1270.05057arXiv1108.6038OpenAlexW2052788654MaRDI QIDQ360359FDOQ360359

Authors: Jang Soo Kim 

Publication date: 26 August 2013

Published in: Annals of Combinatorics (Search for Journal in Brave)

Abstract: Seo and Shin showed that the number of rooted trees on $[n+1]$ such that the maximal decreasing subtree with the same root has $k+1$ vertices is equal to the number of functions $f:[n]o[n]$ such that the image of $f$ contains $[k]$. We give a bijective proof of this theorem.

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

Recommendations

• On the enumeration of rooted trees with fixed size of maximal decreasing trees
• A remark on the enumeration of rooted labeled trees
• Bijective proofs of the hook formula for rooted trees.
• A new bijection on rooted forests
• Enumerations of vertices among all rooted ordered trees with levels and degrees

zbMATH Keywords

bijectionsmaximal decreasing subtreesrooted trees

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A refinement of Cayley's formula for trees
• A combinatorial proof of {P}ostnikov's identity and a generalized enumeration of labeled trees
• A generalized enumeration of labeled trees and reverse Prüfer algorithm
• A combinatorial basis for the free Lie algebra of the labelled rooted trees
• Title not available (Why is that?)
• On the enumeration of rooted trees with fixed size of maximal decreasing trees

Cited In (5)

• Fishburn trees
• Tree/endofunction bijections and concentration inequalities
• Decomposition of triply rooted trees
• On the enumeration of rooted trees with fixed size of maximal decreasing trees
• Construction and composition of rooted trees via descent functions

This page was built for publication: Bijections on rooted trees with fixed size of maximal decreasing subtrees

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