Generating function for planted planar trees

I need your help to solve this problem :


Give a generating function for planted planar trees with all degrees odd.

Show that the number of such trees with $2k+1$ non-root vertices is
$$\displaystyle \frac{\binom{3k}{k}}{(2k+1)}$$


Please help !

Solutions Collecting From Web of "Generating function for planted planar trees"

Start by computing the generating function for the odd total degree
trees without the degree-one root node. There is an even number of children plus a link to the parent for a total odd degree. This has the functional
equation
$$T(z) = z + z \frac{T(z)^2}{1-T(z)^2}.$$

Now recall the Lagrange Inversion Formula as presented e.g. at this
MathWorld link
(consulted May 26 2014.)

Using their variables we have $w=z$, $\alpha=z$ and
$$\phi(w) = \frac{w^2}{1-w^2}.$$

Setting $F(v) = v$ in the above we obtain
$$T(z) = z + \frac{z}{1} \frac{z^2}{1-z^2}
+ \frac{z^2}{2!} \frac{\partial}{\partial z}
\left(\frac{z^2}{1-z^2}\right)^2
+ \frac{z^3}{3!} \frac{\partial^2}{\partial z^2}
\left(\frac{z^2}{1-z^2}\right)^3
+ \cdots.$$
Recall that
$$\left(\frac{z}{1-z}\right)^q
= \sum_{n\ge q} {n-1\choose q-1} z^n$$
so that
$$\left(\frac{z^2}{1-z^2}\right)^q
= \sum_{n\ge q} {n-1\choose q-1} z^{2n}.$$
This implies that
$$\frac{\partial^{q-1}}{\partial z^{q-1}}
\left(\frac{z^2}{1-z^2}\right)^q
= \sum_{n\ge q} (2n)^{\underline{q-1}}
{n-1\choose q-1} z^{2n-(q-1)}.$$
This in turn yields
$$[z^m] \frac{z^q}{q!}\frac{\partial^{q-1}}{\partial z^{q-1}}
\left(\frac{z^2}{1-z^2}\right)^q
\\= [z^m] \frac{z^q}{q!}
\sum_{n\ge q} (2n)^{\underline{q-1}} {n-1\choose q-1} z^{2n+1-q}
\\ = \frac{1}{q!} [z^{m-q}]
\sum_{n\ge q} (2n)^{\underline{q-1}} {n-1\choose q-1} z^{2n+1-q}.$$

If $m$ is odd this gives $2n+1=m$ and we must have $(m-1)/2\ge q$ for
a contribution of
$$\frac{1}{q!} (m-1)^{\underline{q-1}}{m/2-3/2\choose q-1}.$$

Collecting everything into one formula we obtain for $m\ge 3$ and $m$
odd the closed form
$$1 + \sum_{q=2}^{m/2-1/2} \frac{1}{q!}
(m-1)^{\underline{q-1}}{m/2-3/2\choose q-1}$$
which is
$$1 + \sum_{q=2}^{m/2-1/2} \frac{1}{q!}
\frac{(m-1)!}{(m-q)!}
{m/2-3/2\choose q-1}$$
or equivalently
$$1 + \frac{1}{m}
\sum_{q=2}^{m/2-1/2} {m\choose q} {m/2-3/2\choose q-1}.$$

Simplifying this to
$$\frac{1}{m}{3m/2-3/2\choose m/2-1/2}$$
is best done with a CAS and Zeilberger’s algorithm /
Sister Celine’s method.

This is the following sequence
$$ 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, 1430715, \ldots$$
which is OEIS A001764 where
a variety of relevant information can be found.

Addendum Tue May 27 22:12:28 CEST 2014.

Here is some additional material to document how to obtain the simple
closed form.

Note that we can absorb the term in front into the sum, turning
$$1 + \frac{1}{m}
\sum_{q=2}^{m/2-1/2} {m\choose q} {m/2-3/2\choose q-1}$$
into
$$\frac{1}{m}
\sum_{q=1}^{m/2-1/2} {m\choose q} {m/2-3/2\choose q-1}.$$
Now since $m$ is odd put $m=2k+1$ to get
$$\frac{1}{2k+1}
\sum_{q=1}^k {2k+1\choose q} {k-1\choose q-1}.$$

It turns out that Maple has an implementation of creative telescoping,
the method we cited above. In the present case it yields the following
data:

> restart;
> with(SumTools[DefiniteSum]):
> CreativeTelescoping(binomial(2*k+1,q)*binomial(k-1,q-1),q=1..k);
                       1/2   k
                      3    27  GAMMA(k + 1/3) GAMMA(k + 2/3)
                  1/2 --------------------------------------
                                Pi GAMMA(2 k + 1)

Now using the multiplication theorem of the
Gamma function
we have that
$$\Gamma(k+1/3)\Gamma(k+2/3)
=\frac{2\pi\times 3^{1/2-3k}}{\Gamma(k)} \Gamma(3k).$$
Substituting this into the closed form for the sum yields
$$\frac{1}{2\pi}
\frac{3^{1/2+3k}}{\Gamma(2k+1)}
\frac{2\pi\times 3^{1/2-3k}}{\Gamma(k)} \Gamma(3k)
= \frac{3k\Gamma(3k)}{k\Gamma(k)\Gamma(2k+1)}.$$
It follows that the closed form for the number of trees is
$$\frac{1}{2k+1}
\frac{3k\Gamma(3k)}{k\Gamma(k)\Gamma(2k+1)}
= \frac{(3k)!}{(k!)\times (2k+1)!}
= \frac{1}{2k+1} \frac{(3k)!}{(k!)\times (2k)!}
= \frac{1}{2k+1} {3k\choose k}.$$

Note that the method of creative telescoping provides sound proof of
the closed forms of the sums that it is applied to as explained e.g. by
Wilf in his book generatingfunctionology.

As it turns out the Mathworld formulation is not optimal here. We can do better using Wilf’s formulation as given in generatingfunctionology.

Re-write the functional equation like this:
$$T(z)-T(z)^3 = z – z T(z)^2 + z T(z)^2 = z.$$
Now we have
$$[z^n] T(z) = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z) dz$$
and make the substituion $w = T(z)$ so that $z=w-w^3$ and $dz = (1-3w^2) dw$ to get
$$ \frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{1}{w^{n+1} (1-w^2)^{n+1}} w (1-3w^2) dw$$
which is
$$ \frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{1}{w^n (1-w^2)^{n+1}} (1-3w^2) dw.$$
Now the Cauchy Residue Theorem gives the following two coefficients for $n=2k+1$ and odd
$$[w^{n-1}] \frac{1}{(1-w^2)^{n+1}}
= [w^{2k}] \frac{1}{(1-w^2)^{n+1}} = {k+n\choose n} = {3k+1\choose 2k+1}$$
and
$$[w^{n-1}] 3w^2 \frac{1}{(1-w^2)^{n+1}}
= 3 [w^{2k-2}] \frac{1}{(1-w^2)^{n+1}} = 3{k-1+n\choose n} = 3{3k\choose 2k+1}.$$
But $${3k+1\choose 2k+1} – 3{3k\choose 2k+1} = \frac{1}{2k+1}{3k\choose k}$$
and we are done.