Flajolet and Sedgewick: Asymptotic expression for the coefficients of alignments

50 Views Asked by At

In Analytic Combinatorics (p.261, Chapter IV, 4ed) by Flajolet and Sedgewick. The authors state that for

$$O(z) = \frac{1}{1-\log \frac{1}{1-z}}$$

holds

$$O(z) \sim \frac{-e^{-1}}{z-1+e^{-1}}$$

and therefore

$$[z^n]O(z) \sim \frac{e^{-1}}{(1-e^{-1})^{n+1}}.$$

However, I do not understand this at all. Could you please explain this to me?

1

There are 1 best solutions below

1
On BEST ANSWER

It is easy to observe that $z_0 = 1 - e^{-1}$ is a pole of $O(z)$ (Substitute $z_0$ into $O(z)$ results $O(z_0) = \frac{1}{0}$.)

And $O(z)$ can be expressed as $O(z) = \frac{f(z)}{g(z)}$ where $f(z) = 1$ and $g(z) = 1 - \log \frac{1}{1 - z}$. Then,

\begin{align} O(z) &\sim \frac{1}{z - z_0} \cdot \frac{1}{g^{'}(z_0)} \\ &= \frac{e^{-1}}{z - 1 + e^{-1}} \end{align}

where $g^{'}(z) = -\frac{1}{1-z}$. Then, the coefficient is estimated as

\begin{align} [z^n]O(z) \sim -\frac{1}{g^{'}(z_0)} \cdot \frac{1}{z_0^{n+1}} \tag{1} \end{align}

Substitute $z_0$ and $g^{'}(z_0)$ into (1) reaches the desired result.