Counting vertices in plane and $k$-ary trees with given outdegree

Abstract

We count the number of vertices in plane trees and $k$-ary trees with given outdegree, and prove that the total number of vertices of outdegree $i$ over all plane trees with $n$ edges is $\left(\genfrac{}{}{0ex}{}{2n-i-1}{n-1}\right)$, and the total number of vertices of outdegree $i$ over all $k$-ary trees with $n$ edges is $\left(\genfrac{}{}{0ex}{}{k}{i}\right)\left(\genfrac{}{}{0ex}{}{kn}{n-i}\right)$. For both results we give bijective proofs as well as generating function proofs.

8 pages, 3 figures, deleted generating function proofs of the two main theorems, and added Theorem 3.9

References in corpus (1)

• Enumerations of vertices among all rooted ordered trees with levels and degrees