Bijections on rooted trees with fixed size of maximal decreasing subtrees

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]\to [n]$ such that the image of $f$ contains $[k]$. We give a bijective proof of this theorem.

9 pages

Cited by in corpus (1)

• On the enumeration of rooted trees with fixed size of maximal decreasing trees