\documentstyle[12pt]{article}
\pagestyle{empty}
\begin{document}
\begin{center}
Math 491, Problem Set \#15 \\
Solutions
\end{center}
\medskip
\begin{enumerate}
\item[(a)]
{\it Let $A_n$ be the average number of times
that a $2n$-step Dyck path
returns to the origin
(counting $(2n,0)$ as a return but not $(0,0)$),
so that $A_0 = 0$, $A_1 = 1$, $A_2 = 3/2$, and $A_3 = 9/5$.
Use Maple to compute $A_n$
for various small values of $n$ (1 through 6, at least),
and conjecture a general formula.}
Let us create a two-variable generating function
in which a $2n$-step Dyck path
that returns to the horizontal axis exactly $k$ times
is given weight $x^n y^k$.
This generating function is
$1+yP(x)+y^2[P(x)]^2+y^3[P(x)]^3+\dots=1/(1-yP(x))$,
where $P(x)$ is the generating function
for primitive Dyck paths.
Since a primitive Dyck path
is the same thing as an up-edge
followed by an arbitrary Dyck path
followed by a down-edge,
we have $P(x) = xD(x)$
where $D(x)$ is the generating function for all Dyck paths.
Since $D(x) = (1 - \sqrt{1-4x})/2x$,
$P(x) = (1 - \sqrt{1-4x})/2$.
So the generating function we want is
$$R(x,y) = \frac{1}{1-y\frac{1-\sqrt{1-4x}}{2}}.$$
If we differentiate this with respect to $y$,
and then put $y=1$,
we'll obtain a generating function in which
the coefficient of $x^n$ is the sum,
over all Dyck paths of length $n$,
of the number of returns to the horizontal axis.
We have
$$R'_2(x,1) = 2\:\frac{1-\sqrt{1-4x}}{(1+\sqrt{1-4x})^2}$$
(where $R'_2(x,1)$ means the derivative of $R(x,y)$ with respect to
its second variable, evaluated at $y=1$).
Using Maple, we write
\begin{verbatim}
Q := 1/(1-y*(1-sqrt(1-4*x))/2);
R := subs(y=1,Q);
S := subs(y=1,diff(Q,y));
Rt := taylor(R,x,10);
St := taylor(S,x,10);
seq(coeff(St,x,n)/coeff(Rt,x,n),n=0..9);
\end{verbatim}
and obtain the sequence of fractions
0, 1, 3/2, 9/5, 2, 15/7, 9/4, 7/3, 12/5, 27/11.
Multiplying by 2,3,4,... respectively, we get
0, 3, 6, 9, 12, 15, 18, 21, 24, 27,
which we recognize.
So we conjecture that the coefficient of $x^n$ in {\tt{St}},
divided by the coefficient of $x^n$ in {\tt{Rt}},
equals $3n/(n+2)$.
That is, the average number of returns to the horizontal axis
is exactly $3n/(n+2)$.
\item[(b)]
{\it Give an algebraic proof of your conjecture using generating functions.}
Now let's see how Maple can help us prove the theorem.
We have two generating functions, $A(x)$ and $B(x)$,
where $$A(x)=\frac{1-\sqrt{1-4x}}{2x}$$
and $$B(x) = 2\:\frac{1-\sqrt{1-4x}}{(1+\sqrt{1-4x})^2}.$$
We want to show that their respective coefficients
satisfy $b(n) = \frac{3n}{n+2} a(n)$.
That is, we want to prove
$$(n+2)b(n) = (3n)a(n).$$
Let's prove this by turning both sides into generating functions.
If we differentiate $B(x)=\sum_{n \geq 0} b(n)x^n$ we get
$\sum_{n \geq 0} nb(n)x^{n-1}$,
so $\sum_{n \geq 0} (n+2)b(n)x^n = xB'(x) + 2B(x)$.
Likewise
$\sum_{n \geq 0} (3n)a(n)x^n = 3xA'(x)$.
So we'll be done if we can demonstrate that
$(x+2)B(x)=3xA(x)$.
How can Maple help us prove this?
One thing we definitely shouldn't do is define $A(x)$ and $B(x)$
as functions of $x$!
Maple knows how to simply algebraic expressions,
not programs or functions.
Even if we define things as expressions, we can still go astray.
For instance, it might seem sensible to proceed like this:
\begin{verbatim}
A := (1-sqrt(1-4*x))/(2*x);
B := 2*(1-sqrt(1-4*x))/(1+sqrt(1-4*x))^2;
evalb(x*diff(B,x)+2*B=3*x*diff(A,x));
\end{verbatim}
Maple returns the answer {\tt{false}}, because it doesn't see
a reason why the two should be equal.
We haven't asked Maple to work hard at simplifying either side,
so why should it?
(I still haven't figured out which simplifications Maple
does without one's asking;
my version of Maple says {\tt{x+y=y+x}} is true
but {\tt{(x-y)*(x+y)=x*x-y*y}} is ``false''.)
A better question to ask Maple
(after defining {\tt{A}} and {\tt{B}}) is
\begin{verbatim}
evalb(simplify(x*diff(B,x)+2*B)=simplify(3*x*diff(A,x)))
\end{verbatim}
But Maple still says this is false
(because Maple has no standard form for algebraic functions of $x$,
and so it simplifies the two sides of the equation
in two different ways).
The best way to get Maple to go all-out and try to prove
that two things are equal
is to ask it to simplify the difference (to see if it gets 0)
or to simplify the quotient (to see if it gets 1).
But even that sometimes fails!
Maple is a partner in doing algebra,
not an infallible genii.
In this case,
{\tt simplify((x*diff(B,x)+2*B)-(3*x*diff(A,x)))}
gives 0 (which proves the theorem),
{\tt simplify((x*diff(B,x)+2*B)/(3*x*diff(A,x)))}
doesn't give 1 (which fails to prove the theorem.
(Note:
\begin{verbatim}
expand(1/(simplify((x*diff(B,x)+2*B)/(3*x*diff(A,x)))));
\end{verbatim}
{\it does\/} give 1, so that's another way to prove the theorem.)
% Note to self, 10/26/01:
% Another approach goes as follows:
% Look at the total number of times
% the Dyck path achieves its original height,
% including its initial position
% (this is 1 more than the quantity defined in the problem).
% It turns out that if we sum THIS quantity over all Dyck paths
% of length 2n, we get the total number of Dyck paths of length 2n+2!
% So, if we prove this combinatorially (I'm not sure how to do this yet),
% or we do it algebraically (via recurrence relations),
% we we find that the quantity that the problem asks about is just
% the ratio of the n+1st Catalan number to the nth, minus 1.
\item[(c)]
{\it Give a bijective proof of your conjecture,
using the relationship between
Dyck paths and triangulations of polygons.}
Recall that every Dyck path of length $2n$ can be put into correspondence
with a unique triangulation of the $n+2$-gon.
The number of returns of the Dyck path to the line $y=0$
is the same as the number of triangles
incident with the left endpoint of the base-edge.
Thus the average number of returns to the line $y=0$
(as we vary over all Dyck paths of length $2n$)
is the same as the average number of such triangles
(as we vary over all triangulations of the $(n+2)$-gon).
But this quantity (call it $a$) has to be the same at every vertex.
If we multiply $a$ by $n+2$ (the number of vertices),
we should get the average total number of triangles in the triangulation,
multiplied by 3 (since each vertex is incident with exactly 3 triangles).
But the total number of triangles in each triangulation of the $(n+2)$-gon
is exactly $n$.
So we have $a(n+2)=3n$, giving us $a=3n/(n+2)$.
\end{enumerate}
\end{document}