Heap-ordered Trees, 2-Partitions and Continued Fractions

This paper studies the enumerations and some interesting combinatorial properties of heap-ordered trees (HOTs). We first derive analytically the total numbers of n-node HOTs. We then show that there exists a 1-1 and onto correspondence between any two of the following four sets: the set of (n + 1)-node HOTs, the set of 2-partitions of Z2n = {1, 2,…, 2n} the set of Young tableaux from Z2n without odd-length columns, and set of weighted paths of length 2n. These correspondence can not only be used to obtain the above enumeration quantities through combinatorial arguments, but can also relate their generating functions to continued fractions.