Generating function for vertices distance from the root in a planar tree

I need you help to solve this problem:


Consider a planar tree with $n$ non-root vertices.

  1. Give a generating function for vertices distance $d$ from the root.
  2. Proof that the total number is $$\displaystyle \binom{2n}{n-d}\frac{2d+1}{(n+d+1)}$$

We are supposed to have an exponential generating function then use Lagrange Inversion Theorem…


Solutions Collecting From Web of "Generating function for vertices distance from the root in a planar tree"

What we want here is ordinary generating functions since we are
working with unlabeled trees. Start by computing the generating
function $T_n(z)$ for ordered planar trees of at most a given height
$n$ classified according to the nodes of a distance $d$ from the root
(variable $u_d$) and the total number of nodes (variable $z$), where
the singleton node has height zero, to get

$$T_0(z) = u_0 z \quad\text{and}\quad
T_n(z) = u_0 z + u_0 z \times
\left.\frac{T_{n-1}(z)}{1-T_{n-1}(z)}
\right|_{u_0=u_1, u_1=u_2,\ldots}.$$

It then follows that the generating function $G_d(z)$ of the number of
nodes of a distance $d$ from the root in all ordered planar graphs on
$n$ nodes is given by
$$G_d(z) = \left.\frac{\partial}{\partial v}
T_d(z)(u_0=1, u_1=1, \ldots u_{d-1}=1, u_d = v\times Q(z)/z)
\right|_{v=1}.$$

Here $Q(z)$ generates ordered trees on $n$ nodes and has the
functional equation
$$Q(z) = z + z\frac{Q(z)}{1 – Q(z)}
= z \frac{1}{1-Q(z)}.$$
Re-write this as
$$Q(z) = z + Q(z)^2.$$

We use $Q(z)/z$ in the substitution because when we attach a tree at a node of depth $d$ we get two overlapping nodes, one of which we remove.

We defer the detailed analysis of $T_d(z)$ to a later time and show
how to compute the coefficients of $G_4(z).$
We have
$$T_4(z)=
{\frac { \left( {z}^{2}u_{{2}}u_{{4}}-zu_{{2}}-zu_{{3}}-zu_{{4}}+1
\right) u_{{0}}z}{{z}^{2}u_{{1}}u_{{3}}+{z}^{2}u_{{1}}u_{{4}}+{z}^{2}
u_{{2}}u_{{4}}-zu_{{1}}-zu_{{2}}-zu_{{3}}-zu_{{4}}+1}}$$
and hence
$$G_4(z)=
\frac{z^4 Q(z)}
{(2 Q(z)z – Q(z) + z^2 -3z + 1)^2}.$$

We use Lagrange inversion as presented by Wilf in
generatingfunctionology, in particular his notes on why the
following computation is valid.

We have for $n\ge 5$
$$[z^n] G_4(z) =
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{n+1}}
\frac{z^4 Q(z)}
{(2 Q(z)z – Q(z) + z^2 -3z + 1)^2} dz.$$
Now put $w=Q(z)$ so that $$z=w-w^2$$ so that the denominator becomes
$$(2 w \times w (1-w) – w + w^2(1-w)^2 -3w(1-w) + 1)^2
= (1-w)^8$$ to obtain
$$\frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{1}{w^{n+1}(1-w)^{n+1}}
\frac{w^4 (1-w)^4 \times w}
{(1-w)^8} (1-2w) dw$$
which is
$$\frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{1}{w^{n-4}(1-w)^{n+5}}
(1-2w) dw.$$
By the Cauchy Residue Theorem this works out to be
$${n-5 + n+4 \choose n+4} – 2 {n-6 + n+4\choose n+4}
={2n-1 \choose n+4} – 2{2n-2 \choose n+4} \\
={2n-2\choose n-5}\frac{9}{n+4}.$$

This $n$ represents classification by the total number of nodes. If we
classify by the number $m$ of non-root nodes then $n=m+1$ and we get
$${2m\choose m-4}\frac{9}{m+5}.$$

This MSE link points to another Lagrange inversion computation.

I am including some Maple code for those readers who want to explore the generating functions that appear here. (Not guaranteed to be optimized.) The function names are the same as in the text above.


with(combinat);

part_count :=
proc(part)
      local m, q;

      m := map(p->op(2,p), convert(part, multiset));
      multinomial(nops(part), seq(m[q], q=1..nops(m)));
end;

gf_nolabel :=
proc(n)
       option remember;
       local p, gf, sgf, k, prd;

       if n=1 then return u[0] fi;

       gf := 0;
       for p in partition(n-1) do
           sgf := mul(gf_nolabel(p[k]), k=1..nops(p));
           sgf := subs([seq(u[k]=u[k+1], k=0..n-1)], sgf);

           gf := gf + expand(u[0]*sgf*part_count(p));
       od;

       gf;
end;

gf_nolabel_all :=
proc(n)
       option remember;
       local k;

       subs([seq(u[k]=1, k=0..n-1)], gf_nolabel(n));
end;

gf_nolabel_d :=
proc(n, d)
       option remember;
       local k, res;

       res := gf_nolabel(n);
       res := subs([seq(u[k]=1, k=0..d-1)], res);
       res := subs([seq(u[k]=1, k=d+1..n-1)], res);

       subs(u[d]=1, diff(res, u[d]));
end;

Q := op(2, [solve(T=z+z*T/(1-T), T)]);

catalan := n -> binomial(2*n,n)/(n+1);

T :=
proc(d)
       option remember;
       local k, sgf;

       if d=0 then return u[0]*z fi;

       sgf := T(d-1);
       sgf := subs([seq(u[k]=u[k+1], k=0..d-1)], sgf/(1-sgf));

       factor(u[0]*z*(1+sgf));
end;

T_subs :=
proc(d)
       local sgf;

       sgf := subs([seq(u[k]=1, k=0..d-1), u[d]=v*T], T(d));
       factor(subs(v=1, diff(sgf, v)));
end;

Addendum Sun Jun 1 22:48:52 CEST 2014. By request we now give
explicit formulas for $T_n(z).$

Introduce the sets $U_{p, q, l}$ which is the sum of all products of
$l$ terms in the variables $u_d$ with $d$ being at least $p$ and at
most $q$ where the presence of $u_d$ in a term means that $u_{d+1}$ is
not present in the term (minimum index gap is two).

Then we can show by induction that
$$T_d(z) =
\frac{u_0 z \sum_{k=0}^{\lfloor d/2\rfloor} (-1)^k z^k U_{2,d,k}}
{\sum_{k=0}^{\lceil d/2\rceil} (-1)^k z^k U_{1,d,k}}.$$
Making the substitution $u_0=1, u_1=1, \ldots u_{d-1}=1, u_d =v$
this becomes
$$F_d(z) =
\frac{z \sum_{k=0}^{\lfloor d/2\rfloor} (-1)^k z^k |U_{2,d-1,k}|
+ z v \sum_{k=0}^{\lfloor d/2\rfloor} (-1)^k z^k |U_{2,d-2,k}|\times (-z)}
{\sum_{k=0}^{\lceil d/2\rceil} (-1)^k z^k |U_{1,d-1,k}|
+ v \sum_{k=0}^{\lceil d/2\rceil} (-1)^k z^k |U_{1,d-2,k}|\times (-z)}.$$

Here we must have $2\le d-2$ so what follows is valid for $d\ge 4.$

Observe that the cardinality of $U_{1,q,k}$ can be calculated with the
generating function
$$[z^q] \frac{1}{1-z} \times
\frac{z}{1-z}\left(\frac{z^2}{1-z}\right)^{k-1}
= [z^q] \frac{z^{2k-1}}{(1-z)^{k+1}} \\=
[z^{q-(2k-1)}] \frac{1}{(1-z)^{k+1}}
= {q-(2k-1)+k \choose k} = {q-k+1\choose k}.$$
Similarly the cardinality of $U_{2,q,k}$ can be calculated with the
generating function
$$[z^q] \frac{1}{1-z} \times
\frac{z^2}{1-z}\left(\frac{z^2}{1-z}\right)^{k-1}
= [z^q] \frac{z^{2k}}{(1-z)^{k+1}} \\=
[z^{q-2k}] \frac{1}{(1-z)^{k+1}}
= {q-2k+k \choose k} = {q-k\choose k}.$$
Substitute this into the formula for $F_d(z)$ to obtain
$$F_d(z) =
\frac{z \sum_{k=0}^{\lfloor d/2\rfloor} (-1)^k z^k {d-1-k\choose k}
+ z v \sum_{k=0}^{\lfloor d/2\rfloor} (-1)^{k+1} z^{k+1} {d-2-k\choose k}}
{\sum_{k=0}^{\lceil d/2\rceil} (-1)^k z^k {d-k\choose k}
+ v \sum_{k=0}^{\lceil d/2\rceil} (-1)^{k+1} z^{k+1} {d-1-k\choose k}}.$$

Now we continue as before, attaching $Q(z)/z$ at $v$, differentiating
with respect to $v$ and setting $v=1.$
This gives for the denominator of $G_d(z)$ the formula
$$\left(\sum_{k=0}^{\lceil d/2\rceil} (-1)^k z^k {d-k\choose k}
+ Q(z)
\sum_{k=0}^{\lceil d/2\rceil} (-1)^{k+1} z^k {d-1-k\choose k}\right)^2.$$
For the numerator we get
$$Q(z)
\left(
\sum_{k=0}^{\lfloor d/2\rfloor} (-1)^{k+1} z^{k+1} {d-2-k\choose k}
\right)
\\\times
\left(\sum_{k=0}^{\lceil d/2\rceil} (-1)^k z^k {d-k\choose k}
+ Q(z) \sum_{k=0}^{\lceil d/2\rceil} (-1)^{k+1} z^k {d-1-k\choose k}
\right)
\\-
\left(
z \sum_{k=0}^{\lfloor d/2\rfloor} (-1)^k z^k {d-1-k\choose k}
+ Q(z) \sum_{k=0}^{\lfloor d/2\rfloor} (-1)^{k+1} z^{k+1} {d-2-k\choose k}
\right)
\\\times
Q(z) \sum_{k=0}^{\lceil d/2\rceil} (-1)^{k+1} z^k {d-1-k\choose k}.$$

I do not advise to treat the above expression manually but it should
be clear that it can be simplifed using only trivial manipulations of
binomial coefficients, and the result is $$z^d Q(z).$$

Therefore we have established the formula
$$G_d(z) = z^d Q(z)
\left(\sum_{k=0}^{\lceil d/2\rceil} (-1)^k z^k {d-k\choose k}
+ Q(z)
\sum_{k=0}^{\lceil d/2\rceil} (-1)^{k+1} z^k {d-1-k\choose k}\right)^{-2}.$$
Setting up the Lagrange inversion integral as before we use
$$[z^n] G_d(z) =
\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} G_d(z) dz$$
and make the substitution $w=Q(z)$ i.e. $z=w-w^2=w(1-w)$
to get the new integrand
$$(1-2w)\times\frac{1}{w^{n+1} (1-w)^{n+1}}
w^d (1-w)^d\times w\times
\left(\sum_{k=0}^{\lceil d/2\rceil} (-1)^k w^k (1-w)^k {d-k\choose k}
+ w
\sum_{k=0}^{\lceil d/2\rceil} (-1)^{k+1} w^k (1-w)^k {d-1-k\choose k}
\right)^{-2}$$
which simplifies to
$$(1-2w) \frac{1}{w^{n+1} (1-w)^{n+1}} \frac{w^{d+1}}{(1-w)^d}
= \frac{1}{w^{n-d}} \frac{1-2w}{(1-w)^{n+1+d}}.$$
Now apply the Cauchy residue theorem to get
$$[w^{n-d-1}] \frac{1}{(1-w)^{n+1+d}}
-2 [w^{n-d-2}] \frac{1}{(1-w)^{n+1+d}}.$$
Switch to non-root vertices $m$ so that $n=m+1$ for the answer
$$[w^{m-d}] \frac{1}{(1-w)^{m+2+d}}
-2 [w^{m-1-d}] \frac{1}{(1-w)^{m+2+d}}$$ or
$${m-d+m+1+d\choose m+1+d} – 2 {m-1-d+m+1+d\choose m+1+d}$$
which is
$${2m+1\choose m+1+d} – 2 {2m\choose m+1+d}.$$
Simplify one last time to obtain
$${2m\choose m-d}\frac{2d+1}{m+d+1}.$$