A Combinatorial Proof for Identities on an Odd Number and an Even Number of Right Leaves in p-ary Trees

摘要

A binary tree is a plane tree such that each internal vertex has two children. The structure of binary tree is widely used in computer science. The structure of p-ary tree is a generalization of the structure of binary tree such that each internal vertex has p children. This study investigates the number of right leaves in p-ary trees. A leaf is referred as a right leaf if it is the rightmost child of some internal vertex. Moreover, based on p-ary trees, a combinatorial proof of identities related to an odd number and an even number of right leaves in p-ary trees is presented. This study provides an efficient structure for computer and information science and further extensive application of the structure p-ary trees with their right leaves will be investigated in the future.