Combinatorics: How to apply the implicit function scheme?

Question

A rooted dissection of a convex polygon with a distinguished edge (the root) is a set of non-crossing diagonals of the polygon. Let $D_n$ be the class of rooted dissections of regular $(n + 2)$-gons. The ordinary generating function $D(z)$ of $\mathcal{D} = \cup_n D_n$ satisfies

$$D(z) = (1+D(z)) \biggl( \frac{1}{1-z(1+D(z))} - 1 \biggr).$$ Use the implicit function scheme to determine an asymptotic formula for $[z^n]D(z)$.

Remark: You can find the relevant section from the Flajolet & Sedgewick book page 467, 468 below.

I suppose that the exercise is meant to be solved using $$G(z, D(z)) := (1+D(z)) \biggl( \frac{1}{1-z(1+D(z))} - 1 \biggr),$$

i.e. $$G(z, w) := (1+w) \biggl( \frac{1}{1-z(1+w)} - 1 \biggr).$$

However, I do not understand how to apply the scheme. Is it enough to compute the (regular) derivatives $G_z$ and $G_{ww}$, solve the characteristic system, and then plug the results into the formula?

So far I have:

$$\frac{\partial}{\partial w} G(z,w) = -\frac{(w+1)z(wz+z-2)}{(-wz-z+1)^2},$$

so by $G(r,s) = s$ implying $z = \frac{w^2+2w-\sqrt{(w+1)^3} +1}{(w+1)^3}$. Is this correct so far?

Answer 1

For $\bf{I_1}$ and $\bf{I_2}$, note that $$ \frac{{1 + w}}{{1 - z(1 + w)}} = \sum\limits_{m = 0}^\infty {z^m (1 + w)^{m + 1} } = \sum\limits_{m,n = 0}^\infty \binom{m + 1}{n}z^m w^n $$ provided $|z(1+w)|<1$. We can take, for instance, $R=\frac{1}{2}$ and $S=1$. From this you can see that $g_{0,0} = 0$, $g_{0,1} = 0 \ne 1$ and $g_{m,n} > 0$ if $m + 1 \ge n \ge 2$.

For $\bf{I_3}$, you can check that $r = 3 - 2\sqrt 2$ and $s = \frac{{\sqrt 2 }}{2}$ satisfy the requirements. (In fact, they are the unique positive solutions of the characteristic system.)

I leave you as an exercise to show, via Theorem VII.$\bf 3$, that $$ D_n=[z^n ]D(z) = \frac{{\sqrt 2 + 1}}{{2^{7/4} \sqrt \pi \, n^{3/2} }}(3 + 2\sqrt 2 )^n \!\left( {1 + \mathcal{O}\!\left( {\frac{1}{n}} \right)} \right), $$ as $n\to +\infty$.

Remark. The generating function has an explicit expression: $$ D(z) = \frac{{1 - 3z - \sqrt {z^2 - 6z + 1} }}{{4z}}. $$ You can do direct singularity analysis to $D(z)$ to obtain the asymptotics for $D_n$.

Answer 2

Following the work by @Gary we require

$$D_n = - [z^{n+1}] \frac{1}{4} \sqrt{z^2-6z+1} = - \frac{1}{4} \frac{1}{n+1} [z^n] \frac{z-3}{\sqrt{z^2-6z+1}}.$$

We start with

$$[z^n] \frac{1}{\sqrt{z^2-6z+1}} = [z^n] \frac{1}{\sqrt{(z-(3+2\sqrt 2))(z-(3-2\sqrt 2))}}.$$

The singularity that is closest to the origin is in the second square root term and we write

$$\frac{1}{(3-2\sqrt 2)^n} (3-2\sqrt 2)^n [z^n] \frac{1}{\sqrt{(z-(3+2\sqrt 2))(z-(3-2\sqrt 2))}} \\ = (3+2\sqrt 2)^n [z^n] \frac{1}{\sqrt{(z(3-2\sqrt 2)-(3+2\sqrt 2)) (z(3-2\sqrt 2)-(3-2\sqrt 2))}} \\ = \frac{(3+2\sqrt 2)^n}{\sqrt{3-2\sqrt{2}}} [z^n] \frac{1}{\sqrt{(3+2\sqrt 2)-z(3-2\sqrt 2)) (1-z)}}.$$

Extracting the dominant asymptotics as on page 180 of Wilf's generatingfunctionology we get

$$(3+2\sqrt 2)^{n+1/2} {n+1/2-1\choose n} \frac{1}{\sqrt{4\sqrt{2}}} = \frac{1+\sqrt 2}{2^{5/4}} (3+2\sqrt 2)^n {n-1/2\choose n} \\ = \frac{1+\sqrt 2}{2^{5/4}} (3+2\sqrt 2)^n (-1)^n {-1/2\choose n} = \frac{1+\sqrt 2}{2^{5/4}} (3+2\sqrt 2)^n [w^n] \frac{1}{\sqrt{1-w}} \\ = \frac{1+\sqrt 2}{2^{5/4}} (3+2\sqrt 2)^n \frac{1}{4^n} {2n\choose n}.$$

Collecting the two contributions we find

$$(3+2\sqrt 2)^n \frac{1}{4^n} {2n\choose n} \left[-3 + \frac{4}{3+2\sqrt 2} \frac{n^2}{(2n)(2n-1)} \right].$$

The square bracketed constant is asymptotic to

$$-3 + \frac{1}{3+2\sqrt 2} = -3 + 3-2\sqrt{2} = -2^{3/2}.$$

It follows that the first term of the expansion is

$$\frac{1}{4} \frac{1}{n+1} 2^{3/2} \frac{1+\sqrt 2}{2^{5/4}} (3+2\sqrt 2)^n \frac{1}{4^n} {2n\choose n}.$$

Recall the central binomial coefficient has ${2n\choose n} \sim \frac{4^n}{\sqrt{\pi n}}$ so that this becomes

$$\frac{1}{4} \frac{1}{n+1} 2^{3/2} \frac{1+\sqrt 2}{2^{5/4}} (3+2\sqrt 2)^n \frac{1}{\sqrt{\pi n}}.$$

The asymptotic of $1/(n+1)$ is $1/n-1/n^2+\cdots$ and $2+5/4-3/2=7/4$ so that we have at last

$$\bbox[5px,border:2px solid #00A000]{ D_n\sim \frac{1+\sqrt 2}{\sqrt{\pi} 2^{7/4}} (3+2\sqrt 2)^n \frac{1}{n^{3/2}}.}$$