**Views:**

^{13}

**Visibility:**Unlisted (only visible to those who know the link)

**Image:**ubuntu2004

**Kernel:**SageMath 9.5

## Exercises: An Invitation to Analytic Combinatorics in Several Variables

Created by Stephen Melczer

This notebook complements the exercises found on the ALEA ACSV course webpage

A quick Sage tutorial can be found here (try an interactive version in your browser here).

See https://melczer.ca/textbook for further Sage notebooks solving problems in analytic combinatorics in several varibles. In particular, this notebook (also available as a static HTML page) gives an algorithm to compute asymptotic terms. Don't use it to solve these exercises, but use it to further check your answers! (Or to compute asymptotics for other problems!)

These functions can be used to compute the matrix M appearing in asymptotics, as well as the leading asymptotic term in an asymptotic expansion.

Here is an example of their use to find asymptotics for the main diagonal of $1/(1-x-y-z)$.

We can check our asymptotic approximation by computing series terms.

## Question 1: Delannoy Numbers

The *Delannoy number* $d_{a,b}$ is the number of paths from the origin $(0,0)$ to the point $(a,b)$ using only the steps $\textsf{N}=(0,1)$, $\textsf{E} = (1,0)$, and $\textsf{NE}=(1,1)$.

**(a)** Prove the recurrence $$ d_{a,b} =
\begin{cases}
1 &: \text{ if $a=0$ or $b=0$} \ d_{a-1,b} + d_{a,b-1} + d_{a-1,b-1} &:\text{ otherwise} \end{cases} $Conclude that$ D(x,y) = \sum_{a,b\geq0}d_{a,b}x^ay^b = \frac{1}{1-x-y-xy}. $$

**(b)** Use the Main Theorem of Smooth ACSV to find asymptotics of $d_{n,n}$ as the $(1,1)$-diagonal of $D(x,y)$. What are the critical points in the $(1,1)$ direction? Which are minimal?

**(c)** Use the Main Theorem of Smooth ACSV to find asymptotics of the $(r,s)$-diagonal of $D(x,y)$ for any $r,s>0$.

### Function to numerically compute terms in the expansion

Check your computed asymptotics against this function!

## Question 2: Apéry Asymptotics

Recall from lecture that a key step in Apéry's proof of the irrationality of $\zeta(3)$ is determining the exponential growth of the sequence that can be encoded as the main diagonal of $F(x,y,z,t) = \frac{1}{1 - t(1+x)(1+y)(1+z)(1+y+z+yz+xyz)}.$ Use the Main Theorem of Smooth ACSV to find dominant asymptotics of this sequence.

### Function to numerically compute terms in the expansion

Check your computed asymptotics against this function!

## Question 3: Pathological Directions

**(a)** Find asymptotics of the $(r,s)$-diagonal of $F(x,y) = \frac{1}{1-x-xy}$ for any $0<s<r$.

**(b)** What are the critical points of $F(x,y) = \frac{1}{1-x-xy}$ in the $(r,s)$ direction when $0<r \leq s$? Which are minimal? Characterize the behaviour of the $(r,s)$ diagonal when $0<r \leq s$.

### Function to numerically compute terms in the expansion

Check your computed asymptotics against this function!

## Question 4: A Composition Limit Theorem

An *integer composition* of size $n\in\mathbb{N}$ is an ordered tuple of positive integers (of any length) that sum to $n$. A composition can be viewed as an integer partition where the order of the summands matters. Let $c_{k,n}$ denote the number of compositions of size $n$ that contain $k$ ones.

**(a)** If you know the symbolic method, species theory, or similar enumerative constructions, prove that $C(u,x) = \sum_{n,k\geq0}c_{k,n}u^kx^n = \frac{1-x}{1-2x-(u-1)x(1-x)}.$

**(b)** Prove that the distribution for the number of ones in a composition of size $n$ satisfies a local central limit theorem as $n\rightarrow\infty$. More precisely, find a constant $t>0$ and normal density $\nu_n(s)$ such that $\sup_{s \in \mathbb{Z}} |t^nc_{s,n} - \nu_n(s)| \rightarrow 0$ as $n\rightarrow\infty$.

### Function to plot series coefficients

Check your computed distribution against this function!