# Total number of leaves binary tree with n internal nodes

Using the definition of a leaf as being an internal node with no children (both children are external nodes), how can I find the total number of leaves for all binary trees with n internal nodes, for any n.

I know the number of binary trees with n internal nodes is given by Catalan numbers however I can't work out how to enumerate all $C_n$ trees for each n to find number of leaves (as defined above).

Thanks for any help!

• "Using the definition of a leaf as being an internal node with no children" This doesn't make sense. A leaf has no children and internal node is typically called a branch and has children. – N8tron May 31 '18 at 18:50
• @N8tron I took that from Sedgewick and Flajolet, regardless in this case I'm considering a leaf an internal node with both children external nodes – user2201609 May 31 '18 at 19:08
• Okay now that I've caught onto your notation. I'm going to share a link that can help that make more sense to people using the standard definitions. Note though that even S & F use the standard definition in their appendix ;) algo.inria.fr/flajolet/Publications/book.pdf – N8tron May 31 '18 at 19:24
• @N8tron thanks, I should've made it more clear I was not looking at the standard definition – user2201609 May 31 '18 at 19:31
• Do you want to consider isomorphism classes of rooted trees or any tree? or do you want to consider isomorphism classes at all? – N8tron May 31 '18 at 19:34