# Relationship between ordered and binary trees

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!

-
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

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.
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$.