Lagrange inversion theorem: Difference between revisions

Revision as of 16:21, 15 May 2006

Revision as of 16:36, 15 May 2006

Line 88:

This is the alternate form.

==Example calculation II==

Consider the set <math>\mathcal{bB}</math> of unlabelled binary plane [[tree_Tree_(graph_theory)|trees.]].

An element of <math>\mathcal{B}</math> is either a leaf of size zero, or a root node with two subtrees (planar, i.e. no symmetry between them). The [[Fundamental theorem of combinatorial enumeration]] (unlabelled case) applies.

The group acting on the two subtrees is <math>E_2</math>, which contains a single permutation consisting of two fixed points. The set <math>\mathcal{B}</math> satisfies

:<math>\mathcal{B} = 1 + \mathcal{Z}\mathfrak{S}_2(\mathcal{B}).</math>

This yields the functional equation of the OGF <math>B(z)</math> by the number of internal nodes:

:<math>B(z) = 1 + z B(z)^2 \mbox{ or } z = \frac{B(z)-1}{B(z)^2}.</math>

Let <math>B_{\ge 1}(z) = B(z) - 1</math> to obtain

:<math>z = \frac{B_{\ge 1}}{(B_{\ge 1}-1)^2}.</math>

==Fa&agrave; di Bruno's formula==