Three's a crowd Reloaded

The interesting part of this problem is finding the generating function of $a_n$ , which turns out to be $a(x) = \frac {(1 - x)^2 \sqrt{1 + x + x^2}}{x^2 \sqrt{1 - 3x + x^2}} - \frac 1{x^2}.$ From this closed form, we can figure out that the radius of convergence for the series $\sum a_n x^n$ is $(3 - \sqrt 5)/2$ . The asymptotic growth rate of $a_n$ is the reciprocal of this radius, so $\lim_{n \rightarrow \infty} \frac {a_{n + 1} - a_n}{a_n} = \left( \lim_{n \rightarrow \infty} \frac {a_{n + 1}}{a_n} \right) - 1 = \left( \frac {3 - \sqrt 5}2 \right)^{-1} - 1 = \frac {1 + \sqrt 5}2.$

Now we will show that $a(x)$ is in fact the generating function of $a_n$ . Let $r_{m,n}$ and $b_{m,n}$ denote the numbers of arrangements with $m$ red balls and $n$ black balls ending with a red ball and a black ball, respectively, and let $r(x,y)$ and $b(x,y)$ be the generating functions of $r_{m,n}$ and $b_{m,n}$ . We can obtain any sequence ending in a red ball by appending one or two red balls to the empty sequence or to a sequence ending with a black ball (vice versa for sequences ending in a black ball). This recurrence relation can be expressed in terms of the generating functions with the equations $r(x,y) = \big[ 1 + b(x,y) \big] (x + x^2) \quad \text{and} \quad b(x,y) = \big[ 1 + r(x,y) \big] (y + y^2).$ Let $s_{m,n}$ denote the total number of arrangements with $m$ red balls and $n$ black balls. Then $s_{m,n}$ is equal to $1$ (if $m = n = 0$ ) or to $r_{m,n} + b_{m,n}$ , so the generating function of $s_{m,n}$ is $s(x,y) = 1 + r(x,y) + b(x,y)$ . From the recurrence relation between $r(x,y)$ and $b(x,y)$ , we can show $s(x,y) = \frac {(1 + x + x^2)(1 + y + y^2)}{1 - (x + x^2)(y + y^2)}.$ This generating function has a bivariate series $\sum s_{m,n} x^m y^n$ , and we are interested in the diagonal coefficients of this series because $s_{n,n} = a_n$ . Define the function $g(z,x) = s(z \sqrt x, \sqrt{x}/z) = \frac {(z^2 + z \sqrt x + x)(1 + z \sqrt x + z^2 x)}{z^2(1 - x - x^2) - z(1 + z^2)x \sqrt x},$ and notice that the series for $g$ can be regarded as a Laurent series in $z$ whose coefficients are themselves power series in $\sqrt x$ : $g(z,x) = \sum_{m,n \geq 0} s_{m,n} \left(\sqrt x\right)^{m + n} z^{m - n} = \sum_{k \in \mathbb{Z}} \left( \sum_{m - n = k} s_{m,n} \left( \sqrt x \right)^{m + n} \right) z^k.$ When $m = n$ , we have $\sum_{m - n = 0} s_{m,n} \left( \sqrt x \right)^{m + n} = \sum_{n \geq 0} a_n x^n,$ so the power series of $a_n$ is the coefficient of $z^0$ in the Laurent series for $g$ . The Cauchy integral formula allows us to find coefficients of the Laurent series for $g$ using contour integrals of $g$ . For a suitably small counterclockwise path $\gamma$ around $z = 0$ along which the Laurent series of $g$ converges, $\sum_{n = 0}^\infty a_n x^n = \frac 1{2 \pi i} \int_\gamma \frac {g(z)}z\, dz,$ and by the residue theorem, $\int_\gamma \frac {g(z)} z\, dz = 2\pi i \sum \text{Res}_{z_k(x)} \left( \frac {g(z)}z \right),$ where the summation is taken over all the poles $z_k(x)$ of $g(z)/z$ for which $z_k(x) \rightarrow 0$ as $x \rightarrow 0$ . Altogether, this means that we can find $\sum a_n x^n$ by adding the residues of certain poles of $g(z)/z$ . To find the poles, multiply the denominator of $g$ by $z$ , set the product equal to 0, and solve for $z$ . There are three solutions, but only two of them have a limit of 0 as $x \rightarrow 0$ , $z_0(x) = 0 \quad \text{and} \quad z_1(x) = \frac {1 - x - x^2 - \sqrt{1 - 2x - x^2 - 2x^3 + x^4}}{2x \sqrt x},$ whose residues are $-\frac 1{x^2} \quad \text{and} \quad \frac {(1 - x)^2 \sqrt{1 + x + x^2}}{x^2 \sqrt{1 - 3x + x^2}}.$ Thus we have shown that $a(x)$ is the generating function of $a_n$ as we claimed: $\sum_{n = 0}^\infty a_n x^n = \frac {(1 - x)^2 \sqrt{1 + x + x^2}}{x^2 \sqrt{1 - 3x + x^2}} - \frac 1{x^2} = a(x).$

This application of complex analysis was new to me when I solved this problem. The procedure is outlined by Richard Stanley in Section 6.3 of Enumerative Combinatorics . It is also discussed in some detail by Qiaochu Yuan in a post on his blog and it is applied directly to a variation of the current problem in a post on StackExchange .