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

arXiv1501.07468MaRDI QIDQ6258604FDOQ6258604

Authors: Rosena R. X. Du, Jia He, Xueli Yun 

Publication date: 29 January 2015

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 $2n-i-1choosen-1$, and the total number of vertices of outdegree $i$ over all $k$-ary trees with $n$ edges is $kchooseiknchoosen-i$. For both results we give bijective proofs as well as generating function proofs.

Mathematics Subject Classification ID

Trees (05C05) Exact enumeration problems, generating functions (05A15)

This page was built for publication: Counting vertices in plane and $k$-ary trees with given outdegree

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