Lagrange inversion theorem: Difference between revisions

Revision as of 14:11, 23 November 2021

Revision as of 14:16, 23 November 2021

Line 111:

===Binary trees===

Consider<ref>{{cite book |last1=Harris|first1= John |last2=Hirst |first2= Jeffry L.| last3= Mossinghoff| first3= Michael |date=2008 |title=Combinatorics and Graph Theory |publisher= Springer |page=185-189 |isbn=978-0-387-7977100387797114}}</ref> the set <math>\mathcal{B}</math> of unlabelled [[binary tree]]s. An element of <math>\mathcal{B}</math> is either a leaf of size zero, or a root node with two subtrees. Denote by <math>B_n</math> the number of binary trees on <math>n</math> nodes.

Removing the root splits a binary tree into two trees of smaller size. This yields the functional equation on the generating function <math>\textstyle B(z) = \sum_{n=0}^\infty B_n z^n\text{:}</math>