Regarding Egorychev integrals for binomial coefficients

Question

I've been searching for references that deals with the Egorychev methods and particularly with the integral representations for binomial coefficients.

$$\binom{n}{k}=\frac{1}{2\pi i} \oint_{|z|<\infty}\frac{(1+z)^n}{z^{k+1}}dz$$ and $$\binom{n}{k}=\frac{1}{2\pi i} \oint_{|z|<1}\frac{dz}{(1-z)^{k+1}z^{n-k+1}}$$ My doubt here is, when to use each one? I've seen problems here on MSE where both are used but couldn't figure out when to choose over another. Also I managed to get (?) a sketch of a proof but i would like to see this in the depth it deserves, and there's where I haven't had luck finding references. I am aware of Marko Riedel pdf about the Egorychev method and the Egorychev book itself. But there's no more besides these? And why isn't this more popular and used? I don't remember seeing these results in complex analysis books (not that I can remember at least).

Anyway, thanks in advance if anyone can answer the question about when to use each case and/or conditions to consider to choose.

Answer 1

Ordering of machinery

This is, as the reader may have noticed, a profound question. The introduction by Markus Scheuer is very good work. Here are some comments that may help to continue exploring. First, the Egorychev method has three stages, Egorychev I, which is formal power series, Egorychev II, which is Egorychev's residue calculus as presented in the book, and Egorychev III, complex variables, also as in the book. These are ordered by subset inclusion. The reader should try them in turn. So use complex variables only when necessary (last). This classification originates with Hosam Mahmoud and is presented in a recent paper, to be found at the following Springer link. At this time my compilation is in chronological order and presents Egorychev III before Egorychev I and II.

Types of binomial coefficients

What integrals and contours to use depends on the behavior of the binomial coefficient that is desired. For example with the first one

$${a\choose b} = \frac{1}{2\pi i} \oint_{|z|=\rho} \frac{(1+z)^a}{z^{b+1}} \; dz.$$

we can actually get two types of binomial coefficients. We have with $0\lt\rho\lt 1$ that we obtain a zero value when $b\lt 0$ because the pole at zero has disappeared. But now when $a\lt 0$ and $a\gt b$ a new pole appears at $z=-1.$ Therefore when $1\lt \rho \lt \infty$ we get the value

$$\frac{1}{2\pi i} \oint_{|z|=\rho} \frac{1}{(1+z)^{-a}} z^{-b-1} \; dz \\ = \frac{1}{2\pi i} \oint_{|z|=\rho} \frac{1}{(1+z)^{-a}} \sum_{q=0}^{-b-1} {-b-1\choose q} (1+z)^q (-1)^{-b-1-q} \; dz \\ = {-b-1\choose -a-1} (-1)^{a-b} = {-b-1 \choose a-b} (-1)^{a-b} = {a\choose a-b}.$$

This is the definition that Maple uses, giving e.g. ${-6\choose -8} = 21.$ With $a\ge b$ the falling factorial applies, as in, $a^{\underline{a-b}}/(a-b)!$. Nonetheless it must be pointed out that there are combinatorial problems where the first type is wanted. Egorychev lists four integrals on page 26 of the book to evaluate a single binomial coefficient in a certain sum, choosing the one that features the first type.

Example of two types of integrals

There is a post of mine at this MSE link 4597569 where we can compare the two integrals and their effects on the computation. This appears to be a problem that requires Egorychev III and cannot be done with Egorychev I and II. The two computations are very similar where effort and inputs are concerned and we would not necessarily prefer one over the other. It would seem there is no alternative to doing both once sums of a certain complexity enter into the game. As an additional observation, should an infinite series appear that corresponds to an expansion about infinity the pole at the origin could vanish. In that case, choose a different representation that yields an expansion about zero. We do this all the time with Egorychev I, because formal power series have no notion of converging in a certain contour. Sometimes we choose the representation that makes the rule $[z^{n-k}] f(z) = [z^n] z^k f(z)$ go through because it means we may move the coefficient extractor outside of the sum.

Answer 2

Keywords to look for applications of this kind are residue calculus and Cauchy integral formula in books of combinatorics.

OPs examples taken from Marko Riedels paper are two useful representations of the binomial coefficient $\binom{n}{k}$ using the residue calculus, which is used here as technique to extract a coefficient of a series expansion.

• In the first case we select the coefficient of $z^k$ from the polynomial $(1+z)^n$. We obtain \begin{align*} \frac{1}{2\pi i} \oint_{|z|<\infty}\frac{(1+z)^n}{z^{k+1}}dz &=[z^k](1+z)^n\color{blue}{=\binom{n}{k}}\tag{1} \end{align*}

• In the second case we select the coefficient of $z^{n-k}$ from the binomial series expansion $(1-z)^{-k-1}$ at $z=0$. We obtain \begin{align*} \frac{1}{2\pi i} \oint_{|z|<1}\frac{dz}{(1-z)^{k+1}z^{n-k+1}}\ &=[z^{n-k}](1-z)^{-k-1}\\ &=[z^{n-k}]\sum_{q=0}^{\infty}\binom{-k-1}{q}(-z)^q\\ &=\binom{-k-1}{n-k}(-1)^{n-k}\\ &\,\,\color{blue}{=\binom{n}{k}}\tag{2} \end{align*}

Here we also use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ of a series. On the other hand, whenever we see this operator $[z^k]$ in use we can interpret it as application of the residue calculus in disguise.

Note: It is usually a matter of experience which of the representations $(1+z)^n$ in (1) or $(1-z)^{-k-1}$ in (2) is the right choice for an appropriate simplification of the expression under consideration.

Some references:

• Mathematics for the Analysis of Algorithms by D. H. Greene and D. E. Knuth. In section 4.3.2 Residue Calculus there are examples for the Hadamard product and the diagonalisation of series. Given \begin{align*} F(w,z)=\sum_{m,n\geq 0}\binom{m+n}{n}w^mz^n=\frac{1}{1-w-z} \end{align*} we have the diagonalisation of $F(w,z)$: \begin{align*} G(z)=\frac{1}{2\pi i}\oint_{C}\frac{dt}{(1-t-z/t)t}=\sum_{n}{\binom{2n}{n}}z^n \end{align*}

• Combinatorial Enumeration by I. P. Goulden and D. M. Jackson. In section I.2.3 An Identity (by Residue Composition) the residue calculus is used to show the identity \begin{align*} \sum_{k=0}^{n}\binom{2n+1}{2k+1}\binom{j+k}{2n}=\binom{2j}{2n} \end{align*}

• Advanced Combinatorics by L. Comtet. We find already in Section I.12: Formal Series the diagonalisation example, but here in the context of formal power series.

• Enumerative Combinatorics, Vol. II by R. P. Stanley This classic presents besides many other examples of the residue calculus also the diagonalisation example in section 6.3 Diagonals which contains a thorough treatment of this theme.

• Generating Functionology by H. S. Wilf. See for instance Cauchy's formula which is formula (2.25) in section 2.4 Power Series, Analytic Theory.

• Analytic Combinatorics by P. Flajolet and R. Sedgewick. Here I finally like to cite Theorem IV.4 from section IV.2 Analytic and meromorphic functions:

  • Theorem IV.4 (Cauchy's Coefficient Formula). Let $f(z)$ be analytic in a region $\Omega$ containing $0$ and let $\lambda$ be a simple loop around $0$ in $\Omega$ that is positively oriented. Then, the coefficient $[z^n]f(z)$ admits the integral representation \begin{align*} \color{blue}{f_n\equiv [z^n]f(z)=\frac{1}{2i \pi}\int_{\lambda}f(z)\frac{dz}{z^{n+1}}}. \end{align*}