\documentclass[12pt]{article}
%\pagestyle{empty}
\begin{document}
\begin{center}
Math 192r, Problem Set \#12: Solutions\\
\end{center}
\medskip
\begin{enumerate}
\item
{\it We consider directed animals
on the modified square lattice
that has an extra edge joining $(i,j)$ to $(i+1,j+1)$
for all $i,j$.
A subset $S$ of the first quadrant is a directed animal on this lattice
if for every point $(i,j)$ in $S$ 
there is a path from $(0,0)$ to $(i,j)$ in $S$
via steps of the form $(+1,0)$, $(0,+1)$, $(+1,+1)$.
Let $a_n$ be the number of directed animals on this lattice
having $n$ elements,
so that $a_1=1$, $a_2=3$, $a_3=10$, etc.
Mimic the method discussed in class for the ordinary square lattice
to derive a formula for the generating function 
$\sum_{n=1}^{\infty} a_n$,
and use this to obtain a formula for $a_n$ itself
as well as a formula for $\lim_{n \rightarrow \infty} a_n^{1/n}$.}

We can define pyramids and half-pyramids as before.
The only difference is that it is now possible for
a dimer to be above another dimer 
with exactly the same horizontal position
(in the earlier situation,
the two dimers would have to be offset by 1 position
relative to one another).
So the generating functions for pyramids and half-pyramids
now satisfy the relations
$$P(x) = Q(x) + P(x)Q(x)$$
and
$$Q(x) = x + 2xQ(x) + x[Q(x)].$$
(The factor of 2,
not present in the case of the ordinary square lattice,
arises because when we place a half-pyramid above a dimer
to obtain a half-pyramid,
there are now two different ways to position it.)
Solving these two equations simultaneously
we get
$$Q(x) = \frac{1-2x-\sqrt{1-4x}}{2x} 
= x + 2 x^2 + 5 x^3 + 14 x^4 + ...$$
and
$$P(x) = \frac{\frac{1}{\sqrt{1-4x}}-1}{2} 
= x + 3 x^2 + 10 x^3 + 35 x^4 + ... .$$
We conclude that the number of such animals
is $a_n = {2n \choose n}/2$, so that
$\lim_{n \rightarrow \infty} a_n^{1/n} = 4$
(by an easy application of Stirling's formula).

This problem is adapted from the article
{\it Lattice animals and heaps of dimers\/}
by Mireille Bousquet-M\'elou and Andrew Rechnitzer,
to appear in the journal Discrete Mathematics.

% In the future, include a bijective proof: did anyone find it?

\item
\begin{itemize}
\item[(a)]
{\it The mapping from the ring of formal power series to itself
that sends $f(x)$ to $1+x^2[f(x)]^3$
has a unique fixed point.
Conjecture a formula for the coefficients
of this formal power series.
(Hint: Try to express the ratio of the coefficients
of $x^{2n}$ and $x^{2n-2}$ as a rational function of $n$.)}

Suppose $f_1$ and $f_2$ are both solutions;
say the first place at which they disagree
is at the coefficient of $x^{n}$.
Then $[f_1(x)]^3$ and $[f_2(x)]^3$
agree up to the coefficient of $x^{n-1}$,
so that $1+x^2[f_1(x)]^3$ and $1+x^2[f_2(x)]^3$
agree up to the coefficient of $x^{n+1}$.
But since these expressions equal $f_1(x)$ and $f_2(x)$ respectively,
we find that $f_1$ and $f_2$ agree in their coefficient of $x^n$,
contradicting out choice of $n$.

It follows as it did in the lecture
that a fixed point exists
(since, as a base case,
we can get the constant term to stabilize
by setting it equal to 1).

The fixed point is moreover an attractor:
the same reasoning used above shows that
if $f$ is the fixed point
and $g$ is any formal power series that agrees with $f$
up to the coefficient of $x^{n-1}$,
then $1+x^2[g(x)]^3$ agrees with $f$ up to the coefficient of $x^n$
(and indeed farther).
So we may take $g(x)=1$ as our initial estimate
and repeatedly apply the operation
\begin{verbatim}
taylor(x^2*%^3+1,x,21)
\end{verbatim}
obtaining after ten steps a truncated power series
that is stable under the operation,
whose non-zero coefficients are
1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, and 1430715.
(It is easy to see that the coefficient must vanish
whenever the exponent is odd.)

If we take the ratio of each non-vanishing coefficient to the one before, 
we get the ratios
1, 3, 4, 55/12, 273/55, 68/13, 38/7, 759/136, 325/57, and 29/5.
Multiplying these by
$2 \times 3$, $4 \times 5$, $6 \times 7$, ..., $20 \times 21$ 
respectively, 
we get 6, 60, 168, 330, 546, 816, 1140, 1518, 1950, 2436,
whose $k$th term is $3(3k-2)(3k-1)$.
Hence we conjecture that
the coefficient of $x^{2n}$ is
$$\prod_{k=1}^{n} \frac{3(3k-2)(3k-1)}{(2k)(2k+1)},$$
which can also be written as
$\prod_{k=1}^{n} \frac{(3k)(3k-1)(3k-2)}{(k)(2k+1)(2k)}$,
which reduces to
$(3n)!/n!(2n+1)!$,
or ${3n \choose n}/(2n+1)$.

\item[(b)]
{\it There exist Laurent series
$$g(x) = x^{-1} - \frac{1}{2} - \frac{3}{8}x 
- \frac{1}{2}x^2 - \dots$$
and
$$g(-x) = - x^{-1} - \frac{1}{2} + \frac{3}{8}x 
- \frac{1}{2}x^2 + \dots$$
that are also fixed under that mapping.
Find the first dozen non-vanishing coefficients of $g$
and conjecture a formula for the coefficient of $x^n$.}

Any $g$ that is fixed under the mapping
that sends $f(x)$ to $1+x^2[f(x)]^3$
must satisfy
$g(x)=1+x^2[g(x)]^3$,
which is equivalent to
$x^2 [g(x)]^3 = g(x) - 1$,
which is equivalent to
$$g(x) = \frac{1}{x^2 g(x)} - \frac{1}{x^2 [g(x)]^2},$$
so that $g(x)$ must also be fixed under the mapping
that sends $f(x)$ to $$\frac{1}{x^2 f(x)} - \frac{1}{x^2 [f(x)]^2}.$$
This operation on formal Laurent series
isn't quite what is wanted, but it comes close;
if one iterates this operation,
one observes that the lowest-order coefficient that isn't stable
under iteration oscillates between two values.
This suggests that we instead consider the operation
that sends a formal Laurent series $f$ to the formal Laurent series
$$\frac12 \left( f(x) + \frac{1}{x^2 f(x)} - \frac{1}{x^2 [f(x)]^2} \right).$$
Note that $f(x) = x^{-1}$ is a fixed point of this operation
modulo higher powers of $x$.
To study the behavior of iterates of this operation,
it is helpful to rewrite $f$ as $x^{-1}F$
where $F$ is an actual power series,
and to rewrite the operation as one that sends $F$ to
$$\frac12 (F + 1/F - x/F^2).$$
Suppose $F$ and $G$ are power series with constant term 1
that first disagree at the coefficient of $x^{n}$;
say $G(x)=F(x)(1+cx^{n}+O(x^{n+1}))$, with $c \neq 0$.
Then $1/G(x) = (1/F(x))(1-cx^{n}+O(x^{n+1}))$,
and since the constant term of $1/F$ is 1,
$1/G-1/F = -cx^{n} + O(x^{n+1})$.
Likewise, we have
$1/G^2-1/F^2 = -2cx^{n} + O(x^{n+1})$
so that
$x/G^2-x/F^2 = O(x^{n+1})$.
We also have $G-F = cx^{n} + O(x^{n+1})$.
Combining, we find that
$\frac12 (G + 1/G - x/G^2) - \frac12 (F + 1/F - x/F^2) = 
\frac12 \left( (G-F) + (1/G-1/F) -x (x/G^2 - x/F^2) \right)
= O(x^{n+1})$,
so that $\frac12 (F + 1/F - x/F^2)$ and $\frac12 (G + 1/G - x/G^2)$
agree at the coefficient of $x^n$.
Hence the mapping is a contraction in the $q$-adic metric.
Since the operation $F \mapsto \frac12 (F + 1/F - x/F^2)$
sends the set of power series with constant term 1 into itself,
this set of power series contains a unique fixed point of the mapping.

Iteration of the mapping 
\begin{verbatim}
series((1/2)*(%+1/(x^2*%)-1/(x^2*%^2)),x,14);
\end{verbatim}
(starting from the initial value {\tt{1/x}})
gives us
\begin{eqnarray*}
g(x) & = & 1/x - (1/2) - (3/8)x - (1/2)x^2 - (105/128)x^3 
- (3/2)x^4 \\
& & - (3003/1024)x^5 - (6)x^6 - (415701/32768)x^7 - ... .
\end{eqnarray*}

The coefficient of $x^n$ is apparently always either an integer or a
half-integer when n is even.  If we multiply these half-integers by 2,
we get the numbers 1, 1, 3, 12, 55, 273, \dots encountered in part (a).
Hence for $n=2k$ even, the coefficient of $x^n$ in $g$ is
$-{3k \choose k}/(4k+2)$.

Let's now focus on the coefficients we don't have a formula for yet, 
which (ignoring sign) are 3/8, 105/128, 3003/1024, 415701/32768, 
15935205/262144, and 1302340845/4194304.
Noticing that all the denominators are powers of 2,
we can put the fractions over a denominator that grows systematically,
obtaining 3/8, 105/128, 6006/2048, ...,
with numerators 3, 105, 6006, 415701, 31870410, 2604681690.
If we take the ratios of these integers, we get the fractions
35/1, 286/5, 969/14, 230/3, 899/11, 
which with some effort (and some help from a few two-digit primes)
we can recognize as
$(5 \times 6 \times 7)/(1 \times 2 \times 3)$, 
$(11 \times 12 \times 13)/(2 \times 3 \times 5)$, 
$(17 \times 18 \times 19)/(3 \times 4 \times 7)$, 
$(23 \times 24 \times 25)/(4 \times 5 \times 9)$, 
and 
$(29 \times 30 \times 31)/(5 \times 6 \times 11)$.
So the ratio of the coefficients of $x^{2k+1}$ and $x^{2k-1}$ in $g$
is $$\frac{(6k-1)(6k)(6k+1)}{16(k)(k+1)(2k+1)},$$
which (anticipating the desire to telescope our product)
we may write as
$$\frac{((6k-1)(6k)(6k+1)(6k+2)(6k+3)(6k+4))(k)^2}
{16 (k+1) ((2k)(2k+1))^2 ((3k)(3k+1)(3k+2))}.$$
Then the coefficient of $x^{2k+1}$ equals the coefficient of $x^1$
(namely, $-3/8$) times
$$\frac{((6k+4)!/4!)(k!)^2}{16^k (k+1)! (2k+1)!^2 (3k+2)!/2!},$$
so the final answer comes out to be
$$- \ \frac{(6k+4)!k!}{2^{4k+5} (2k+1)!^2 (3k+2)!}/(k+1).$$

Final remarks:

1) How did I recognize 35/1, 286/5, 969/14, 230/3, and 899/11
as $(5 \times 6 \times 7)/(1 \times 2 \times 3)$, 
$(11 \times 12 \times 13)/(2 \times 3 \times 5)$, 
$(17 \times 18 \times 19)/(3 \times 4 \times 7)$, 
$(23 \times 24 \times 25)/(4 \times 5 \times 9)$, 
and 
$(29 \times 30 \times 31)/(5 \times 6 \times 11)$?
I made the assumption that these ratios could be expressed in the form
$p(n)/q(n)$ where $p,q$ are polynomials of small degree
that factor nicely.  Under this assumption,
the sequence of observed denominators 1,5,14,3,11
should be ``close to'' at least one arithmetic progression,
where we say two numbers are close if one of them divides the other
or their ratio is a ratio of small whole numbers.
In this case, a ``nearby'' arithmetic progression is 3,5,7,9,11,
and I was on my way to an exact formula.
Likewise, the sequence of numerators 
$5 \times 7$, $2 \times 11 \times 13$, 
$3 \times 17 \times 19$, $2 \times 5 \times 23$, $29 \times 31$
suggested that I look for an arithmetic progression
whose first term is 1, 5, or 7, 
whose second term is 2, 11, 13, 22, or 26,
whose third term is 3, 17, 19, 51, or 57,
whose fourth term is 2, 5, 10, 23, 46, or 115,
and whose last term is 29 or 31 ---
or a sequence that doesn't meet this conditions
but is nonetheless a ``near miss''.
I scored a direct hit with 5, 11, 17, 23, 29
and a near miss with 7, 13, 19, 25, 31.
Removing the factors 3,5,7,9,11 from the denominators
and the factors 5,11,17,23,29 and 7,13,19,25,31 from the numerators,
the ratios to be matched by an exact formula become
$(35/1) \times (3/35) = 3$,
$(286/5) \times (5/143) = 2$,
$(969/14) \times (7/323) = 3/2$,
$(230/3) \times (9/575) = 6/5$, and
$(899/11) \times (11/899) = 1$.
To handle the decreasing sequence 3, 2, 3/2, 6/5, 1, 
I took a hint from the denominator 5
and assumed that the denominators coming from the formula
would be 2, 3, 4, 5, and 6.
Multiplying through by these numbers gave
$3 \times 2 = 6$,
$2 \times 3 = 6$,
$(3/2) \times 4 = 6$,
$(6/5) \times 5 = 6$,
$1 \times 6 = 6$ ---
a pattern which is hard to ignore,
and which gives the final piece of the puzzle.

2) If I hadn't been so confident that the numerators and denominators
in the formula for the ratio would factor into linear factors,
I might have used the method of undetermined coefficients.
I would have first tried to write the ratios
$r_1 = 35/1$, $r_2 = 286/5$, $r_3 = 969/14$, $r_4 = 230/3$, $r_5 = 899/11$
in the form $p(n)/q(n)$ where $p,q$ are polynomials of degree 1.
Then, if that failed (and it would!), I would try polynomials of degree 2.
That is, I'd conjecture that
$r_n = (an^2+bn+c)/(dn^2+en+f)$.
Since there are six unknowns here, we first need
to use Maple to compute $r_6 = 1110/13$.
It would be a big chore to solve for $a,...,f$ by hand,
but with Maple it isn't so hard.
Let's suppose we've already got the ratios
$r_1 = 35/1$ through $r_6 = 1110/13$
stored as {\tt{r[1]}} through {\tt{r[6]}}.
We would then enter
\begin{verbatim}
eqnlist:={seq(r[n]=(a*n^2+b*n+c)/(d*n^2+e*n+f),n=1..6)};
solve(eqnlist,{a,b,c,d,e,f});
\end{verbatim}
to obtain the one-parameter family of solutions
$a=108d$, $b=0$, $c=-3d$, $d=d$, $e=3d/2$, $f=d/2$.
Putting $d=2$ we get
$a=216$, $b=0$, $c=-6$, $d=2$, $e=3$, $f=1$,
or $$r_n = \frac{216n^2-6}{2n^2+3n+1} = \frac{6(6k-1)(6k+1)}{(k+1)(2k+1)}.$$

3) Can anyone think of a combinatorial relationship between
the generating functions considered in parts (a) and (b)?

\end{itemize}

\end{enumerate}
\end{document}
