|
Post Made Community Wiki by Anton Geraschenko♦♦
|
||||
|
|
||||
|
1 |
|
||
|
If you're a combinatorialist and you want to know the asymptotics of a sequence $a_n$ with a nice generating function $A(z) = \sum_{n \ge 0} a_n z^n$, the very first thing you should do is find out if $A$ is meromorphic, since then one can analyze the asymptotics of $a_n$ using its poles. Even if $A$ isn't meromorphic, if one has sufficiently good information about its singularities then there are transfer theorems that translate information about the behavior of $A$ near its poles to the behavior of $a_n$ for large $n$. In other words, combinatorialists (and by extension computer scientists) should learn complex analysis. For example, let $E_n$ be the number of alternating permutations on $n$ letters. Then $E(z) = \sum_{n \ge 0} E_n z^n = \sec z + \tan z$ is meromorphic with poles $z = \frac{\pi}{2} + 2k \pi, k \in \mathbb{Z}$. The dominant singularity is at $z = \frac{\pi}{2}$ and one now knows without doing any other computations that $E_n \sim n! \left( \frac{2}{\pi} \right)^n$. Even better one can write down an exact series converging to $E_n$ with one term for each pole. The corresponding expansion of the Bernoulli numbers $B_n$ gives the classical evaluation of the zeta function at even integers. |
||||

