Counting Vertices In κ-ary Trees With A Given Outdegree

Trees are very important combinatorial structures in combinatorics and graph theory. They are not only well-studied by enumerative combinatorialists but also widely applied in bioinformatics and computer science.Deutsch and Shapiro counted the total number of vertices of odd outdegree over all plane trees with n edges and proved that the total number of vertices of odd outdegree over all plane trees with n edges is twice the total number of vertices of outdegree over all plane trees with n edges.In this paper we count the number of vertices in k-ary trees,and prove that the total number of vertices of outdegree i over all k-ary trees with n edges is(k i)(kn n-i).We give generation function proof and bijective proof for this result.