Editing Generating function (section)

===Implicit generating functions and the Lagrange inversion formula===
{{expand section|This section needs to be added to the list of techniques with generating functions|date=April 2017}}

One often encounters generating functions specified by a functional equation, instead of an explicit specification. For example, the generating function {{math|''T(z)''}} for the number of binary trees on {{math|''n''}} nodes (leaves included) satisfies

<math display="block">T(z) = z\left(1+T(z)^2\right)</math>

The [[Lagrange inversion theorem]] is a tool used to explicitly evaluate solutions to such equations.

{{math theorem|Lagrange inversion formula|Let <math display = "inline"> \phi(z) \in C[[z]]</math> be a formal power series with a non-zero constant term. Then the functional equation
<math display = "block">T(z) = z \phi(T(z))</math>
admits a unique solution in <math display = "inline">T(z) \in C[[z]]</math>, which satisfies

<math mode = "block"> [z^n] T(z) = [z^{n-1}] \frac{1}{n} (\phi(z))^n </math>

where the notation <math mode = "inline">[z^n] F(z)</math> returns the coefficient of <math mode = "inline">z^n</math> in <math mode = "\inline">F(z)</math>.
}}

Applying the above theorem to our functional equation yields (with <math display="inline">\phi(z) = 1+z^2</math>):

<math display="block"> [z^n]T(z) = [z^{n-1}] \frac{1}{n} (1+z^2)^n </math>

Via the binomial theorem expansion, for even <math mode="inline">n</math>, the formula returns <math mode="inline">0</math>. This is expected as one can prove that the number of leaves of a binary tree are one more than the number of its internal nodes, so the total sum should always be an odd number. For odd <math mode="inline">n</math>, however, we get

<math mode="block">[z^{n-1}] \frac{1}{n} (1+z^2)^n = \frac{1}{n} \dbinom{n}{\frac{n+1}{2}} </math>

The expression becomes much neater if we let <math mode="inline">n</math> be the number of internal nodes: Now the expression just becomes the <math mode="inline">n</math><sup>th</sup> Catalan number.