3-Zebra Trees

Abstract

An ordered tree, also known as a plane tree or a planar tree, is defined recursively as having a root and an ordered set of subtrees. A $3$-zebra tree is an ordered tree where all edges connected to the root (called height $1$) are tricolored, as are all edges at odd height. The edges at even height are all black as usual.

In this paper, we show that the number of $3$-zebra trees with $n$ edges is equal to the number of Schröder paths with bicolored level steps.