> 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.
$$


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/chapter-5-analytic-combinatorics.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.