> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-aofa/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/chapter-5-analytic-combinatorics.md).

# Chapter 5: Analytic Combinatorics

## Exercise 5.1 🌟

{% hint style="success" %}
This exercise illustrates the symbolic method and its efficacy in simplifying the analysis of combinatorial structures. A formal language is employed to define the combinatorial class, which corresponds to an associated generating function. Extracting coefficients then involves identifying the relevant values pertaining to the object under consideration.
{% endhint %}

Consider the class $$G$$ of binary strings having no three consecutive 0 bits. Such strings are either ∊, a single 0, a double 00, or 1 or 01 or 001 followed by a string with no three consecutive 0 bits. Symbolically, this argument gives the combinatorial construction

$$
G = ∊ + Z\_0 + Z\_0×Z\_0+(Z\_1 + Z\_0 × Z\_1+Z\_0×Z\_0 × Z\_1) × G.
$$

Theorem 5.1 allows us to translate this immediately into a formula for the generating function $$G(z)$$ that enumerates such strings:

$$
G(z) = 1 + z +z^2 + (z + z^2+z^3)G(z) \\
\therefore G(z)=\frac{1+z+z^2}{1-z-z^2-z^3}.
$$

The numerator is consisted of shift factors, as in the example from the book. The denominator is a well-known polynomial describing Tribonacci numbers (see [Exercise 4.18](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/pages/6pjaXyRo8WpOT0GFIIZ1#exercise-4.18)). Therefore, the number of strings of length $$N$$ with no three consecutive 0 bits is $$T\_N+T\_{N+1}+T\_{N+2}=T\_{N+3}$$, a sequence registered under [A000073](https://oeis.org/A000073).

## Exercise 5.2

We can express our class $$G$$ symbolically as

$$
G=SEQ(Z\_1) \times SEQ(Z\_0).
$$

This gives

$$
G(z)=\frac{1}{(1-z)^2} \\\[0.2cm]
\therefore \[z^N]G(z)=N+1.
$$

## Exercise 5.3

This is a simple variation of the example from the book. The class $$U$$ matches the construction

$$
U = Z\_\square + Z\_\blacksquare × U × U.
$$

We translate both $$Z$$ classes as $$z$$ to get

$$
U(z)=z+zU(z)^2 \\\[0.2 cm]
\therefore U(z)=\frac{1-\sqrt{1-4z^2}}{2z}.
$$

{% hint style="info" %}
It’s always wise to check our OGF. For example, WolframAlpha can expand the generating function with `series \frac{1-\sqrt{1-4z^2}}{2z} to order 9`.
{% endhint %}

## Exercise 5.4

The total number of binary trees with $$N$$ nodes is given by the $$N$$th Catalan number. We need to figure out the number of binary trees with $$N$$ nodes without superleaves. The ratio of these numbers specifies the required fraction. The recursive decomposition of our combinatorial structure is

$$
T=Z\_\square+Z\_\blacksquare \times T \times T-Z\_\blacksquare \times Z\_\blacksquare \times Z\_\blacksquare.
$$

Notice that we must exclude a symmetric tree with 3 internal nodes that produces a superleaf at the root. This translates to

$$
T^\blacksquare(z)=1+zT^\blacksquare(z)^2-z^3 \\\[0.2 cm]
\therefore T^\blacksquare(z)=\frac{1-\sqrt{1-4z+4z^4}}{2z}.
$$

With the help of WolframAlpha we can confirm that the coefficients divided by the Catalan numbers produce the desired ratios. There is only one caveat; trees with less than 3 nodes never produce a superleaf, so instead of zero their ratios should give one.

## Exercise 5.5 🌟

{% hint style="success" %}
This exercise introduces a new operation *set of*, where $$B$$ is defined as the collection of all finite subsets of $$A$$.
{% endhint %}

We can regard $$B$$ as a series of independent decisions. The combinatorial construction for a decision $$D$$ about any single object of size $$n$$ in $$A$$ is

$$
D=\epsilon+Z\_n \implies D(z)=1+z^n.
$$

In other words, we either skip it or include it in our collection. Now, if we have $$A\_n$$ distinct objects of size $$n$$ in $$A$$, then we make such decisions for every object. The construction is simply a sequence of $$A\_n$$ decisions that translates to $$(1+z^n)^{A\_n}$$. Finally, the whole product comes from repeating this endeavor for every possible size $$n$$.

The second part of the proof follows from turning a product into a sum by taking a logarithm and employing Taylor expansion of $$\ln(1+x)$$. This gives

$$
\begin{align\*}
B(z) &= \prod\_{n \ge 1}(1+z^n)^{A\_n} \\
&= \exp\bigg{ \sum\_{n \ge 1} A\_n\ln(1+z^n)\bigg} \\
&= \exp\bigg{ \sum\_{n \ge 1} A\_n(z^n-z^{2n}/2+z^{3n}/3- \cdots)\bigg} \qquad \text{(see section 4.2 in the book)} \\
&= \exp\bigg{\sum\_{n \ge 1} A\_nz^n - \frac{1}{2}\sum\_{n \ge 1} A\_n(z^2)^n + \frac{1}{3}\sum\_{n \ge 1} A\_n(z^3)^n - \cdots \bigg} \\
&= \exp\bigg{A(z) - \frac{1}{2}A(z^2) + \frac{1}{3}A(z^3) - \cdots\bigg}.
\end{align\*}
$$

{% hint style="info" %}
The above derivation assumes that $$A\_0=0$$, which is a general precondition for any composition of GFs to be valid (see [Exercise 3.41](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/pages/haY46WTvhNwGF6h7VSOn#exercise-3.41)).
{% endhint %}

## Exercise 5.6 🌟

{% hint style="success" %}
This exercise introduces a new operation *multiset of*, where $$B$$ is defined as the collection of all finite multisets of $$A$$ (subsets with repetitions allowed).
{% endhint %}

We can regard $$B$$ as a series of independent decisions. The combinatorial construction for a decision $$D$$ about any single object of size $$n$$ in $$A$$ is

$$
D=\epsilon+Z\_n+Z\_n \times Z\_n+Z\_n \times Z\_n \times Z\_n + \cdots = SEQ(Z\_n) \implies D(z)=\frac{1}{1-z^n}.
$$

In other words, we either skip it, include it once, or twice, or any number of times (infinite geometric series). Now, if we have $$A\_n$$ distinct objects of size $$n$$ in $$A$$, then we make such decisions for every object. The construction is simply a sequence of $$A\_n$$ decisions that translates to $$1/(1-z^n)^{A\_n}$$. Finally, the whole product comes from repeating this endeavor for every possible size $$n$$.

For the second part of the proof, we follow the same approach as in the previous exercise (including the remark about $$A\_0=0$$)

$$
\begin{align\*}
B(z) &= \prod\_{n \ge 1}\frac{1}{(1-z^n)^{A\_n}} \\
&= \exp\bigg{- \sum\_{n \ge 1} A\_n\ln(1-z^n)\bigg} \qquad \text{($\ln 1=0$)} \\
&= \exp\bigg{-\sum\_{n \ge 1} A\_n(-z^n-z^{2n}/2-z^{3n}/3- \cdots)\bigg} \qquad \text{(see section 4.2 in the book)} \\
&= \exp\bigg{\sum\_{n \ge 1} A\_nz^n + \frac{1}{2}\sum\_{n \ge 1} A\_n(z^2)^n + \frac{1}{3}\sum\_{n \ge 1} A\_n(z^3)^n + \cdots \bigg} \\
&= \exp\bigg{A(z) + \frac{1}{2}A(z^2) + \frac{1}{3}A(z^3) + \cdots\bigg}.
\end{align\*}
$$

## Exercise 5.7

The combinatorial construction is

$$
P^\*\_{ODD} = SET(CYC\_1(Z)+CYC\_3(Z)+CYC\_5(Z)+\cdots).
$$

The EGF associated with the combinatorial class $$P^\*\_{ODD}$$ is

$$
\begin{align\*}
P^**{ODD}(z) &= exp\bigg{z+\frac{z^3}{3}+\frac{z^5}{5}+\cdots\bigg} \\\[0.3 cm]
&=exp\bigg{\ln \frac{1}{1-z}-\frac{z^2}{2}-\frac{z^4}{4}-\cdots\bigg} \\\[0.3 cm]
&=\frac{e^{-\sum*{k \ge 1} \frac{z^{2k}}{2k}}}{1-z} \\\[0.3 cm]
&=\frac{e^{\frac{1}{2}\ln (1-z^2)}}{1-z} \\\[0.3 cm]
&=\frac{\sqrt{1-z^2}}{1-z}= \sqrt{\frac{1+z}{1-z}}.
\end{align*}
$$

## Exercise 5.8

Symbolically, we have the construction

$$
G=SEQ(CYC(Z)),
$$

which, by the cycle and sequence rules in Theorem 5.2, gives the EGF

$$
G(z)=\frac{1}{1-\ln \frac{1}{1-z}}=\frac{1}{1+\ln (1-z)}.
$$

## Exercise 5.9

Symbolically, we have the construction that omits an empty sequence

$$
G=CYC(SEQ\_{\ge 1}(Z)),
$$

which, by the cycle and sequence rules in Theorem 5.2, gives the EGF

$$
G(z)=\ln \frac{1}{1-\frac{z}{1-z}}=\ln \frac{1-z}{1-2z}.
$$

## Exercise 5.10

The proof is available on *Analytic Combinatorics* by RS and PF book’s [website](https://ac.cs.princeton.edu/online/slides/AC03-MGFs.pdf) (see slide 12).

## Exercise 5.11

The first part of the proof is

$$
\begin{align\*}
\sum\_{c \in A + B} \frac{z^{|c|}}{|c|!} u^{\text{cost}(c)} &= \sum\_{a \in A} \frac{z^{|a|}}{|a|!} u^{\text{cost}(a)} + \sum\_{b \in B} \frac{z^{|b|}}{|b|!} u^{\text{cost}(b)} \\
&= A(z, u)+B(z, u).
\end{align\*}
$$

For the labeled product $$A \star B$$, we have

$$
\begin{align\*}
\sum\_{c \in A \star B} \frac{z^{|c|}}{|c|!} u^{\text{cost}(c)} &= \sum\_{a \in A} \sum\_{b \in B} \binom{|a| + |b|}{|a|} \frac{z^{|a|+|b|}}{(|a|+|b|)!} u^{\text{cost}(a) + \text{cost}(b)} \\
&= \sum\_{a \in A} \sum\_{b \in B} \frac{(|a| + |b|)!}{|a|!|b|!} \frac{z^{|a|}z^{|b|}}{(|a|+|b|)!} u^{\text{cost}(a)} u^{\text{cost}(b)} \\
&= \left( \sum\_{a \in A} \frac{z^{|a|}}{|a|!} u^{\text{cost}(a)} \right) \left( \sum\_{b \in B} \frac{z^{|b|}}{|b|!} u^{\text{cost}(b)} \right) = A(z, u)B(z, u).
\end{align\*}
$$

Having established both the labelled summation and product, the remainder of the proof proceeds identically to that presented for Theorem 5.2.

## Exercise 5.12

$$
B\_u(z,1)=\frac{z}{(1-(1+u)z)^2}\bigg|\_{u=1}=\frac{z}{(1-2z)^2}=\frac{1}{2},\frac{2z}{(1-2z)^2}.
$$

Thus, the average number of 1 bits in a random bitstring of length $$N$$ is

$$
\frac{\[z^N]B\_u(z,1)}{2^N}=\frac{N2^{N-1}}{2^N}=N/2.
$$

## Exercise 5.13

Symbolically, we have the construction (see the book)

$$
G = \epsilon + Z\_0 + (Z\_1 + Z\_0 × Z\_1) × G.
$$

We should translate each $$Z\_1$$ as $$uz$$, to get

$$
G(z,u)=\frac{1+z}{1-uz(1+z)}.
$$

The cumulative number of 1 bits is

$$
G\_u(z,1)=\frac{z(1+z)^2}{(1-uz(1+z))^2}\bigg|\_{u=1}=\frac{1+z}{(1-z-z^2)^2} - \frac{1+z}{1-z-z^2}.
$$

The second summand is an OGF for $$F\_{N+2}$$. The first summand can be rewritten as

$$
\frac{1+z}{(1-z-z^2)^2}=\frac{1+z}{z^2} \cdot \left(\frac{z}{1-z-z^2} \cdot \frac{z}{1-z-z^2}\right).
$$

The OGF inside parenthesis is a [self-convolution of Fibonacci numbers](https://oeis.org/A001629) (there is a closed-form solution). Hence, after combining all components and simplifying, we get that the average number of 1 bits in a random bitstring of length $$N$$ having no 00 is

$$
\frac{\[z^N]G\_u(z,1)}{F\_{N+2}}=\frac{4NF\_{N+2}-(N+2)F\_N}{5F\_{N+2}}.
$$

## Exercise 5.14

The book contains the formula for the number of derangements $$D\_N$$. We can tweak the combinatorial construction, by marking cycles with $$u$$, to derive the cumulative generating function

$$
D\_u(z, 1) = \underbrace{\frac{e^{-z}}{1-z}}*{\sum*{N \ge 0}D\_N\frac{z^N}{N!}} \underbrace{\left( \ln \frac{1}{1-z} - z \right)}*{\sum*{N \ge 2}(N-1)!\frac{z^N}{N!}} \\\[0.3 cm]
\therefore \frac{N! \[z^N] D\_u(z, 1)}{D\_N} = \frac{\sum\_{k=2}^N \binom{N}{k} (k-1)! D\_{N-k}}{D\_N}.
$$

Informally, we already know from the book, that in a random permutation the average number of cycles is $$H\_N$$. Let $$X$$ be a random variable counting the number of fixed points (unary cycles) in a random permutation with $$N$$ elements. We have $$X=\sum\_kX\_k$$, where $$X\_k$$ is an indicator random variable telling whether the $$k$$th element remains on its current position. Apparently,

$$
\Pr{X\_k=1}=1/N \implies \mathbb{E}\[X]=\sum\_k \Pr{X\_k=1}=1.
$$

Therefore, the average number of cycles in a random derangement for large $$N$$ is $$\sim H\_N-1$$. Of course, this back-of-the-envelope calculation makes some unjustified assumptions about independence of events, but gives an indication about what happens at the limit.

## Exercise 5.15 🌟

{% hint style="success" %}
This exercise illustrates the symbolic method for parameters in great detail.
{% endhint %}

The total number of binary trees with $$N$$ nodes is given by the $$N$$th Catalan number. The recursive decomposition of our combinatorial structure is

$$
T=\epsilon+Z\_\blacksquare+2Z\_\blacksquare \times (T - \epsilon)+Z\_\blacksquare \times (T - \epsilon)^2.
$$

In plain English, a tree is one of the following:

1. An empty tree (external node).
2. A leaf.
3. A root with one non-empty subtree (either left or right).
4. A root with two non-empty subtrees; we must mark this root.

This gives the following BGF

$$
\begin{align\*}
T(z,u) &= 1 + z + 2z(T(z,u)-1) + uz(T(z,u)-1)^2 \\\[0.3cm]
&= \frac{1 - 2z(1-u) - \sqrt{1 - 4z + 4z^2(1-u)}}{2uz}.
\end{align\*}
$$

Finding a partial derivative directly is quite complicated, even with a help of a computer algebra system. Instead, we will use the functional equation. By differentiating it implicitly, we get

$$
T\_u(z,u) = 2zT\_u(z,u) + z(T(z,u)-1)^2 + 2uz(T(z,u)-1)T\_u(z,u) \\\[0.3cm]
\therefore T\_u(z,1)= \frac{z(T(z,1)-1)^2}{1 - 2zT(z,1)}= \frac{z(T(z,1)-1)^2}{\sqrt{1-4z}}=\frac{z^3 T(z,1)^4}{\sqrt{1-4z}}.
$$

Recall that $$T(z)=T(z,1)=1+zT(z,1)^2$$, a standard equation for binary trees. This enables the last simplification. Extracting the coefficient is trivial by employing equation (5.72) from the book [Concrete Mathematics](https://learning.oreilly.com/library/view/concrete-mathematics-a/9780134389974/) by Graham, Knuth and Patashnik

$$
\[z^N]T\_u(z,1)=\binom{2N-2}{N-3} .
$$

{% hint style="info" %}
The aforementioned book is an indispensable source when dealing with convoluted equations, as it contains numerous identities, like the one we’ve just used.
{% endhint %}

The average number of internal nodes in a binary tree of size $$N$$ with both children internal is

$$
\frac{\[z^N]T\_u(z,1)}{\[z^N]T(z,1)}= \frac{(N-1)(N-2)}{2(2N-1)}.
$$

{% hint style="info" %}
The formula checks perfectly for trees in Figure 5.2.
{% endhint %}

## Exercise 5.16

This is a variation of the previous exercise. The only difference is that we must mark the internal node connected to a single non-empty subtree. This gives

$$
\begin{align\*}
T(z,u) &= 1 + z + 2uz(T(z,u)-1) + z(T(z,u)-1)^2 \\\[0.3cm]
&=1-u + \frac{1 - \sqrt{(1-2z(u+1))(1-2z(u-1))}}{2z}.
\end{align\*}
$$

Following the same approach as previously, we arrive at

$$
T\_u(z,1) = \frac{2z^2 T(z,1)^2}{\sqrt{1-4z}}.
$$

Using the same identity as before, we get

$$
\frac{\[z^N]T\_u(z,1)}{\[z^N]T(z,1)}=\frac{2 \dbinom{2n-2}{n-2}}{\cfrac{1}{n+1} \dbinom{2n}{n}} =\frac{n^2-1}{2n-1}.
$$

{% hint style="info" %}
The formula checks perfectly for trees in Figure 5.2.
{% endhint %}

## Exercise 5.17 🌟

{% hint style="success" %}
This exercise demonstrates how the symbolic method helps in finding various moments that would be very difficult to attain by other means.
{% endhint %}

The explicit formula for $$T(z,u)$$ is

$$
\boxed{T(z,u) = \frac{1 - \sqrt{1 - 4z + 4z^2(1-u)}}{2z}}.
$$

We should calculate variance as described in Table 3.5, so we need a second partial derivative

$$
\left. \frac{\partial^2 T(z,u)}{\partial u^2} \right|\_{u=1} = \frac{2z^3}{(1-4z)^{3/2}}.
$$

To find $$p''\_n(1)$$ we should use the following identities

$$
\frac{1}{\sqrt{1-4z}} = \sum \binom{2k}{k} z^k \qquad \text{(from the book, see Chapter 3)} \\\[0.3cm]
\frac{1}{(1-4z)^{3/2}} = \sum \frac{k+1}{2} \binom{2k+2}{k+1} z^k \qquad \text{(by the index multiply operation)}.
$$

This gives (after right-shifting 3 positions due to $$z^3$$ and multplying by two)

$$
p''\_n(1)=(n-2)\binom{2n-4}{n-2}.
$$

Plugging all components (see also the book for $$p'\_n(1)$$) into the formula for variance and simplifying gives

$$
\sigma^2 = \frac{n(n+1)(n-1)(n-2)}{2(2n-1)^2(2n-3)}.
$$

## Exercise 5.18

We can employ the [general Leibniz rule](https://en.wikipedia.org/wiki/General_Leibniz_rule) to get

$$
\[z^N]\frac{e^{-z}}{1-z}=\frac{1}{N!}\left(\sum\_{0 \le k \le N}\binom{N}{k} (-1)^ke^{-z} (N-k)!(1-z)^{-(N-k)-1}\right)\bigg|*{z=0}=\sum*{0 \le k \le N} \frac{(-1)^k}{k!}.
$$

## Exercise 5.19

The root with the smallest modulus is $$1/\phi$$, so $$\beta=\phi$$. It is a simple algebra to show that

$$
\[z^N]\frac{f(z)}{g(z)}\sim\frac{\phi^{N+2}}{\sqrt 5}.
$$

{% hint style="warning" %}
The book incorrectly has $$N$$ in the exponent instead of $$N+2$$.
{% endhint %}

## Exercise 5.20

According to [Exercise 5.2](#exercise-5.2) $$A(z)=\frac{1}{(1-z)^2}$$. Here, $$\beta=1$$, $$\nu=2$$, $$f(1)=1$$ and $$g''(1)=2$$. Based on Theorem 4.1, an approximation for the number of bitstrings having no occurrence of 01 is

$$
\[z^N]\frac{f(z)}{g(z)}\sim N.
$$

## Exercise 5.21 🌟

{% hint style="success" %}
This exercise showcases the methodology of using the radius-of-convergence bounds.
{% endhint %}

Let $$f(z) = \exp\left(\frac{z}{1-z}\right)$$. For the power series expansion of the exponent to converge, we must restrict our domain to $$|z|<1$$ (the criterion for a geometric series to converge). Therefore,

$$
\[z^n]f(z) \le \underset{x \in (0,1)}{\min} \frac{\exp\left(\frac{x}{1-x}\right)}{x^n}.
$$

We should set $$x$$ to balance the growth of the numerator and the denominator as $$n$$ grows. Since we must prove that the bound is a function of $$\sqrt n$$, let’s try

$$
x = 1 - \frac{1}{\sqrt{n}}.
$$

{% hint style="info" %}
This is a bit reminiscent of the trial and error process in finding particular solutions of nonhomogeneous differential equations.&#x20;
{% endhint %}

We’ve

$$
\exp\left(\frac{x}{1-x}\right) = \exp\left(\frac{1 - \frac{1}{\sqrt{n}}}{\frac{1}{\sqrt{n}}}\right) = \exp(\sqrt{n} - 1),
$$

and

$$
\frac{1}{x^n} = \left(1 - \frac{1}{\sqrt{n}}\right)^{-n}= \left(1 - \frac{1}{\sqrt{n}}\right)^{\sqrt n (-\sqrt n)} \le \exp(\sqrt n + 1).
$$

See [Exercise 4.39](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/pages/6pjaXyRo8WpOT0GFIIZ1#exercise-4.39) to understand the last step. All in all, this concludes the proof that

$$
\[z^n]f(z) \le \exp(\sqrt{n} - 1) \cdot \exp(\sqrt{n} + 1) = \exp(2\sqrt{n}).
$$

We aren’t claiming that $$C=2$$ is optimal, just that there is such a constant.

## Exercise 5.22

This is a variation of the previous exercise. Let $$f(z)=\prod\_{k=1}^\infty (1-z^k)^{-1}$$. The radius of convergence is $$|z|<1$$. To deal with the infinite product, we take the natural logarithm and use the Taylor series expansion $$\ln(1-x) = -\sum\_{j=1}^\infty \frac{x^j}{j}$$. This gives

$$
\begin{align\*}
\ln f(x) &= -\sum\_{k=1}^\infty \ln(1-x^k) \\
&= \sum\_{k=1}^\infty \sum\_{j=1}^\infty \frac{x^{jk}}{j} \\
&= \sum\_{j=1}^\infty \frac{1}{j} \sum\_{k=1}^\infty (x^j)^k && \text{(by absolute convergence of sums)} \\
&= \sum\_{j=1}^\infty \frac{1}{j} \frac{x^j}{1-x^j}.
\end{align\*}
$$

To bound this, we can use a standard algebraic identity (recall that $$0 \<x<1$$)

$$
1 - x^j = (1-x)(1 + x + x^2 + \dots + x^{j-1}) \ge (1-x) j x^{j-1}.
$$

Substituting this back into our series

$$
\frac{x^j}{1-x^j} \le \frac{x^j}{(1-x) j x^{j-1}} = \frac{x}{j(1-x)} \le \frac{1}{j(1-x)}.
$$

We’ve

$$
\ln f(x) \le \sum\_{j=1}^\infty \frac{1}{j} \left( \frac{1}{j(1-x)} \right) = \frac{1}{1-x} \sum\_{j=1}^\infty \frac{1}{j^2} = \frac{\pi^2}{6(1-x)} \\
\therefore f(x) \le \exp\left( \frac{\pi^2}{6(1-x)} \right).
$$

We had already encountered the [Basel problem](https://en.wikipedia.org/wiki/Basel_problem), which was applied above. This gives

$$
\[z^n]f(z)  \le \underset{x \in (0,1)}{\min} \frac{f(x)}{x^n} \le \underset{x \in (0,1)}{\min}\exp\left( \frac{\pi^2}{6(1-x)} - n \ln x \right).
$$

Let’s attempt with the same candidate

$$
x= 1 - \frac{1}{\sqrt{n}}.
$$

We’ve

$$
\frac{\pi^2}{6(1-x)} = \frac{\pi^2}{6 \left(\frac{1}{\sqrt{n}}\right)} = \frac{\pi^2}{6} \sqrt{n},
$$

and

$$
-n \ln x = -n \ln\left(1 - \frac{1}{\sqrt{n}}\right) \le n\underbrace{\left( \frac{1}{\sqrt{n}} + \frac{1}{n} \right)}\_{\overset{\text{Taylor expansion of}}{-\ln(1-x)}} = \sqrt{n} + 1.
$$

Our overall bound becomes

$$
\[z^n]f(z) \le \exp\left( \left( \frac{\pi^2}{6} + 1 \right) \sqrt{n} + 1 \right)=O(\exp(C\sqrt n)).
$$

{% hint style="info" %}
For a more precise bound, take a look at the Wikipedia article about the [partition function](https://en.wikipedia.org/wiki/Integer_partition#Partition_function).
{% endhint %}

## Exercise 5.23

The GF from [Exercise 5.7](#exercise-5.7) is

$$
P^\*\_{ODD}(z) = \sqrt{\frac{1+z}{1-z}}.
$$

Theorem 5.5 immediately gives the result with $$\alpha=1/2$$

$$
\[z^N]P^\*\_{ODD}(z) \sim \frac{\sqrt 2}{\sqrt {\pi N}}= \frac{1}{\sqrt {\pi N/2}}.
$$

## Exercise 5.24

For the special case $$f(z) \equiv1$$, the extension of Theorem 5.5 to three terms is available on *Analytic Combinatorics* by RS and PF book’s [website](https://ac.cs.princeton.edu/online/slides/AC06-SA.pdf) (see slide 14). We’ll reuse it for deriving a more precise version of Theorem 5.5.

The asymptotic expansion follows from expanding $$f(z)$$ into a Taylor series about $$z=1$$

$$
f(z) = \sum\_{k=0}^{\infty} \frac{f^{(k)}(1)}{k!} (z-1)^k=\sum\_{k=0}^{\infty} \frac{f^{(k)}(1)}{k!} (-1)^k(1-z)^k.
$$

This gives

$$
\frac{f(z)}{(1-z)^\alpha} = \sum\_{k=0}^{\infty} (-1)^k \frac{f^{(k)}(1)}{k!} (1-z)^{k-\alpha}
\= \sum\_{k=0}^{\infty} (-1)^k \frac{f^{(k)}(1)}{k!} (1-z)^{-(\alpha - k)}.
$$

Substituting the first few terms $$k \in \[0,2]$$ and collecting powers of $$n$$ gives

$$
\begin{align\*}
\[z^n] \frac{f(z)}{(1-z)^\alpha}
&= \frac{n^{\alpha-1}}{\Gamma(\alpha)},f(1) \\
&\qquad + \frac{n^{\alpha-2}}{\Gamma(\alpha-1)}\left( \frac{\alpha}{2},f(1) - f'(1) \right) \\
&\qquad + \frac{n^{\alpha-3}}{\Gamma(\alpha-2)}\left( \frac{\alpha(3\alpha-1)}{24},f(1) - \frac{\alpha-1}{2},f'(1) + \frac{1}{2},f''(1) \right) \\
&\qquad + O!\left(n^{\alpha-4}\right) \\
&=  \frac{n^{\alpha-1}}{\Gamma(\alpha)} f(1) \left\[ 1 + \frac{C\_1}{n} + \frac{C\_2}{n^2} + O(n^{-3}) \right],
\end{align\*}
$$

where

$$
C\_1 = \frac{\alpha(\alpha-1)}{2} - (\alpha-1)\frac{f'(1)}{f(1)}, \\\[0.4cm]
C\_2 = \frac{\alpha(\alpha-1)(\alpha-2)(3\alpha-1)}{24} - \frac{(\alpha-1)^2(\alpha-2)}{2}\frac{f'(1)}{f(1)} + \frac{(\alpha-1)(\alpha-2)}{2}\frac{f''(1)}{f(1)}.
$$

## Exercise 5.25

We follow the steps from the proof of Theorem 5.5

$$
\begin{align\*}
\[z^n]f(z) \ln \frac{1}{1-z} &= \frac{f\_0}{n}+\frac{f\_1}{n-1}+ \cdots +\frac{f\_{n-1}}{1} \\
&= \frac{1}{n} \left(f\_0+\frac{f\_1}{1-1/n}+\frac{f\_2}{1-2/n}+ \cdots +\frac{f\_{k\_0}}{1-k\_0/n}+\cdots+\frac{f\_{n-1}}{1/n}\right) \\
&\sim \frac{1}{n} \sum\_k f\_k = \frac{f(1)}{n}.
\end{align\*}
$$

We’ve split the sum into two parts around the threshold value $$k\_0$$; in spirit, aligned with the Laplace method for sums. A good choice is $$k\_0 = \lfloor \sqrt{n} \rfloor$$; the head of the sum captures all of $$f(1)$$, where the denominators tend to one. Assuming that $$f(z)$$ has a radius of convergence $$r>1$$, all terms indexed larger than $$k\_0$$ tend to zero exponentially fast (recall that $$\[z^n]f(z)=O(r^{-n})$$). Therefore, the tail sum is negligible.&#x20;

## Exercise 5.26

This is a variation of the previous exercise. From Table 3.1 we know that

$$
\[z^n] \frac{1}{1-z} \ln \frac{1}{1-z} = H\_n.
$$

We setup a convolution, just like in the proof of Theorem 5.5 from the book

$$
\[z^n] f(z) \left( \frac{1}{1-z} \ln \frac{1}{1-z} \right) = \sum\_{k=0}^{n} f\_k H\_{n-k}.
$$

We split the sum in the same way as previously, so the leading part is

$$
\sum\_{k=0}^{k\_0} f\_k H\_{n-k} \sim H\_n \sum\_{k=0}^{k\_0} f\_k \sim f(1) \ln n.
$$

This is true, since $$H\_{n-k} \sim H\_n \sim \ln n$$ for large $$n$$ and $$k\le k\_0=\sqrt n$$. The tail sum is negligible for the same reason as in the previous exercise. Therefore,

$$
\[z^n] f(z) \frac{1}{1-z} \ln \frac{1}{1-z} \sim f(1) \ln n.
$$