Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am looking for a formula for the number of ordered trees with $n$ vertices and $l$ leaves as well as for a formula for the number of binary trees with $l$ left and $r$ right children. Finally, I would like to know how those numbers are related and if there is an bijection and if yes how the bijection looks like.

Thank you!

share|improve this question
    
About the bijection, see math.stackexchange.com/questions/66221/… –  Isomorphism Dec 15 '12 at 18:29
    
@Isomorphism: I am looking for a different bijection. The post you linked is about a bijection for full binary trees, whereas I require a bijection for a particular number of left and right children. –  bronko Dec 16 '12 at 9:58

1 Answer 1

up vote 1 down vote accepted

Having $l$ for both leaves and left children might be confusing. Let $L,R$ be the number of left and right children in the binary tree.

There is indeed a bijection between ordered trees and binary trees, called first child next sibling. The nodes are kept the same, but the left binary child points to the first child in the ordered tree, whereas the right child points to the next sibling. (In both cases, insofar these nodes exist.)

The number of nodes in both tree equals $n$. Any tree with $n$ nodes has $n-1$ children in total. Thus the binary tree has a total of $n-1$ child-pointers also. Each leaf in the ordered tree is a node without children. Thus there are $\ell$ nodes without children, i.e., $\ell$ binary nodes without first child, and the remaining $L=n-\ell$ nodes have a left pointer. This accounts for $n-\ell$ children, out of a total $n-1$ children, so the rest must be next siblings, $R=\ell-1$.

Is this, eeeuh, homework?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.