\documentclass{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amsfonts}
\usepackage{amsmath}
\begin{document}
\bigskip
\[
\begin{array}{c}
\text{In Case You Still Don't Know What I Did This Summer}\\
_{\text{by Mark Tiefenbruck}}
\end{array}
\]
\bigskip
Let $\sigma =\sigma _{1}\sigma _{2}\cdots \sigma _{n}$ be a word of length n
such that $\sigma _{1},\dots,\sigma _{n}\in \mathbb{N}$. It shall be assumed that $\sigma _{l}=0$ for all $l$ outside of this range. Then, define the variation of $\sigma $:
\bigskip
\[
var(\sigma )=\sum|\sigma _{i}-\sigma _{i-1}|.
\]
\bigskip
The focus of this discussion will be the enumeration of words based on $var(\sigma )$, with various restrictions placed on the letters of $\sigma $.
\bigskip
\bigskip
Start by defining two sequences of generating functions:
\begin{align}
T_{k}(p,q,z)&=\sum_{i,j,n\geq 0}T_{i,j,n,k}p^{i}q^{j}z^{n}, \nonumber\\
U_{k}(p,q,z)&=\sum_{i,j,n\geq 0}U_{i,j,n,k}p^{i}q^{j}z^{n}. \nonumber
\end{align}
$T_{i,j,n,k}=$ \# of words $\sigma $ of length $n$ such that $0\leq \sigma
_{1},\dots,\sigma _{n}\leq k$, $var(\sigma )=i$, and $\sum\sigma _{l}=j$.
$U_{i,j,n,k}=$ \# of words $\sigma $ of length $n$ such that $1\leq \sigma
_{1},\dots,\sigma _{n}\leq k$, $var(\sigma )=i$, and $\sum\sigma _{l}=j$.
\bigskip
Now I shall present two arguments with which we can form relationships
between these two series.
\bigskip
First, suppose you have a word $\sigma $ of length $n\geq 1$ such that $%
0\leq \sigma _{1},\dots,\sigma _{n}\leq k$. Then, define a new word $%
\sigma ^{\prime }$ of length $n$ such that $\sigma _{l}^{\prime }=\sigma
_{l}+1, 1\leq l\leq n$. It follows that $1\leq \sigma _{1},\dots,\sigma _{n}\leq k+1$,
$var(\sigma ^{\prime })=var(\sigma )+2$ (since $\sigma
_{0}^{\prime }$ and $\sigma _{n+1}^{\prime }$ remain $0$ and all other
differences remain the same), $\sum\sigma _{l}^{\prime
}=n+\sum\sigma _{l}$%
. Now, suppose you have a word of length $0$ and do the same. Clearly,
nothing changes. So, after noting that every word of length $n$ such that $%
1\leq \sigma _{1},\dots,\sigma _{n}\leq k+1$ can be obtained this way, we
conclude that
\bigskip
\begin{equation}
U_{k+1}(p,q,z)=1+p^{2}(T_{k}(p,q,zq)-1)\text{,} \tag{1}
\end{equation}
\bigskip
where the $1$s account for the word of length $0$. Special care should be taken to note that the third argument of $T_{k}$ is $zq$.
\bigskip
Instead, now, suppose you have two words $\sigma $ and $\sigma ^{\prime }$
of lengths $n\geq 0$ and $n^{\prime }\geq 0$ such that $0\leq \sigma
_{1},\dots,\sigma _{n}\leq k$ and $1\leq \sigma _{1}^{\prime
},\dots,\sigma _{n^{\prime }}^{\prime }\leq k$. Let $\sigma ^{\prime
\prime }$ be the concatenation of the two words with a $0$ inserted between
them. Then, $n^{\prime \prime }=n+n^{\prime }+1$, $0\leq \sigma _{1}^{\prime
\prime },\dots,\sigma _{n^{\prime \prime }}^{\prime \prime }\leq k$,
$var(\sigma ^{\prime \prime })=var(\sigma )+var(\sigma
^{\prime })$, and $\sum\sigma _{l^{\prime \prime }}^{\prime \prime }=\sum\sigma
_{l}+\sum\sigma _{l^{\prime }}^{\prime
}$. We see that every word containing at least one $0$ can be obtained in
this manner. Every word that does not contain a $0$ is described by $%
U_{k}(p,q,z)$, so we conclude that
\bigskip
\begin{equation}
T_{k}(p,q,z)=T_{k}(p,q,z)\ast z\ast U_{k}(p,q,z)+U_{k}(p,q,z)\text{.}
\tag{2}
\end{equation}
\bigskip
Equation (1) gives a relationship between $U_{k+1}$ and $T_{k}$, and
equation (2) gives a relationship between $T_{k}$ and $U_{k}$. Therefore, we
have a recurrence relationship for the two generating functions. Now we need
some initial conditions. There are no words of length $n\geq 1$ such that $%
1\leq \sigma _{1},\dots,\sigma _{n}\leq 0$. However, it is essential to
the argument above that there is always one word of length $0$. Therefore,
we may conclude that
\bigskip
\begin{equation}
U_{0}=1\text{.} \tag{3}
\end{equation}
\bigskip
\bigskip
This is wonderful and all, but it would be so much better to have an
explicit formula for $T_{k}$, don't you think? I think so. So. Let's assume,
somewhat arbitrarily but reasonably, after a little bit of work, that $T_{k}$
can be expressed in the form
\bigskip
\[
T_{k}(p,q,z)=\frac{A_{k}(p,q,z)}{B_{k}(p,q,z)}.
\]
\bigskip
Then, we do some algebra, using our recurrence relationships (1) and (2).
\bigskip
\begin{align}
U_{k+1}(p,q,z)&=\frac{(1-p^{2})B_{k}(p,q,zq)+p^{2}A_{k}(p,q,zq)}{B_{k}(p,q,zq)} \nonumber\\
T_{k+1}(p,q,z)&=\frac{(1-p^{2})B_{k}(p,q,zq)+p^{2}A_{k}(p,q,zq)}{(1-z+p^{2}z)B_{k}(p,q,zq)-p^{2}zA_{k}(p,q,zq)}
\nonumber
\end{align}
\bigskip
Therefore,
\bigskip
\begin{align}
A_{k+1}(p,q,z)&=(1-p^{2})B_{k}(p,q,zq)+p^{2}A_{k}(p,q,zq), \tag{4}\\
B_{k+1}(p,q,z)&=B_{k}(p,q,zq)-zA_{k+1}(p,q,z). \tag{5}
\end{align}
$\bigskip $
Also, a quick use of equation (2) with our initial condition (3) tells us
that $T_{0}=\frac{1}{1-z}$. Therefore,
$\bigskip $
\begin{equation}
A_{0}=1,B_{0}=1-z. \tag{6}
\end{equation}
\bigskip
Now, define two more generating functions:
\bigskip
\begin{align}
f(z,x)&=\sum_{k=0}^{\infty }A_{k}x^{k}, \nonumber\\
g(z,x)&=\sum_{k=0}^{\infty }B_{k}x^{k}. \nonumber
\end{align}
\bigskip
Then, using equations (4), (5), and (6),
\bigskip
\begin{align}
f(z,x)&=x(1-p^{2})g(zq,x)+xp^{2}f(zq,x)+1 \tag{7}\\
g(z,x)&=xg(zq,x)-zf(z,x)+1. \tag{8}
\end{align}
\bigskip
Solving for $f$ in (8) and substituting into (7):
\bigskip
\[
q(xg(zq,x)-g(z,x)+1)=zqx(1-p^{2})g(zq,x)+xp^{2}(xg(zq^{2},x)-g(zq,x)+1)+zq
\]
\begin{equation}
q-zq-xp^{2}=qg(z,x)+(zqx(1-p^{2})-qx-xp^{2})g(zq,x)+x^{2}p^{2}g(zq^{2},x)
\tag{9}
\end{equation}
\bigskip
Now, let
\bigskip
\[
g(z,x)=\sum_{i=0}^{\infty }C_{i}(p,q,x)z^{i}\text{.}
\]
\bigskip
Then, substituting into (9) and isolating the coefficients of $z^{i}$,
\bigskip
\[
qC_{i}+q^{i}x(1-p^{2})C_{i-1}-q^{i}(qx+xp^{2})C_{i}+q^{2i}x^{2}p^{2}C_{i}=0,i\geq 2
\]
\begin{equation}
C_{i}=\frac{q^{i}x(p^{2}-1)}{q-q^{i}(qx+xp^{2})+q^{2i}x^{2}p^{2}}%
C_{i-1}=\frac{q^{i}x(p^{2}-1)}{(q-xp^{2}q^{i})(1-xq^{i})}C_{i-1},i\geq 2 \tag{10}
\end{equation}
\[
q-xp^{2}=qC_{0}-(qx+xp^{2})C_{0}+x^{2}p^{2}C_{0}
\]
\begin{equation}
C_{0}=\frac{q-xp^{2}}{q-(qx+xp^{2})+x^{2}p^{2}}=\frac{q-xp^{2}}{%
(q-xp^{2})(1-x)}=\frac{1}{1-x}\text{.} \tag{11}
\end{equation}
\[
-q=qC_{1}+qx(1-p^{2})C_{0}-q(qx+xp^{2})C_{1}+q^{2}x^{2}p^{2}C_{1}
\]
\begin{equation}
C_{1}=\frac{x(p^{2}-1)C_{0}-1}{(1-xp^{2})(1-qx)} \tag{12}
\end{equation}
\bigskip
At this point, it is simple to find an explicit formula for $C_{i}$. If we
first define the shifted factorial:
\bigskip
\[
(a;q)_{n}=(1-a)(1-aq)...(1-aq^{n-1})\text{, (}1\text{ if }n=0\text{)}
\]
\bigskip
then it is clear that
\bigskip
\[
C_{i}=\frac{q^{\binom{i}{2}}x^{i}(p^{2}-1)^{i}}{(xp^{2};q)_{i}(xq;q)_{i}(1-x)%
}-\frac{q^{\binom{i}{2}}x^{i-1}(p^{2}-1)^{i-1}}{(xp^{2};q)_{i}(xq;q)_{i}},
\]
\bigskip
excluding the second term for $i=0$. Further, if we define the basic hypergeometric series:
\bigskip
\[
_{r}\Phi
_{s}(a_{1},...,a_{r};b_{1},...,b_{s};q,z)=\sum_{i=0}^{\infty }\frac{%
(a_{1};q)_{i}...(a_{r};q)_{i}}{(b_{1};q)_{i}...(b_{s};q)_{i}(q;q)_{i}}(q^{%
\binom{i}{2}}(-1)^{i})^{s-r+1}z^{i}\text{,}
\]
\bigskip
then we see that
\bigskip
\begin{equation}
g(z,x)=\frac{(1-xp^{2})_{2}\Phi _{2}(0,q;xp^{2},xq;q,xz(1-p^{2}))}{%
x(1-x)(1-p^{2})}-\frac{1}{x(1-p^{2})}\text{.} \tag{13}
\end{equation}
\bigskip
Substituting this into equation (8) easily gives an expression for
$f(z,x)$ as well. Then, the numerator and denominator of $T_{k}$,
respectively, are the coefficients of $x^{k}$ in $f(z,x)$ and
$g(z,x)$.
\bigskip
\bigskip So this gives fairly explicit formulas for $T_{k}$ and $U_{k}$.
However, hypergeometric series are not so easy to manipulate. Therefore, I
shall present some other interesting results.
\bigskip
Later on, it will be important to know formulas for $T_{k}(1,q,z)$ and $%
U_{k}(1,q,z)$. Substituting $p=1$ in equations (10), (11), and (12), we find
that
\bigskip
\begin{align}
g(z,x)|_{p=1}&=\frac{1}{1-x}-\frac{z}{(1-x)(1-qx)}=\frac{1-qx-z}{(1-x)(1-qx)},
\tag{14}\\
f(z,x)|_{p=1}&=\frac{1}{1-x}. \tag{15}
\end{align}
\bigskip
The standard methods reveal that the coefficient of $x^{k}$ in
equations (14) and (15), respectively, are $1-\frac{z(1-q^{k+1})
}{1-q}$ and $1$. Therefore,
\bigskip
\begin{align}
T_{k}(1,q,z)&=\frac{1-q}{1-q-z(1-q^{k+1})}, \tag{16}\\
U_{k}(1,q,z)&=\frac{1-q}{1-q-z(q-q^{k+1})}. \tag{17}
\end{align}
\bigskip
\bigskip
This is all well and good, but the purpose of this discussion is to address
the topic of variations. Using the derived explicit formula for $T_{k}$, it
is possible to find the exact distribution of variations among words
categorized by length, sum, and bound. However, such computations are
time-consuming and may contain much more information than is actually
needed. So, we can do some analysis and compute the expected variation of an
arbitrarily chosen word with specified length, sum, and bound. We can do
this by summing all of the possible variations for words with those
characteristics and dividing by the total number of words. That is,
\bigskip
\[
E[var(\sigma )]=\frac{\text{coefficient of }q^{j}z^{n}\text{ in }\frac{\partial T_{k}}{\partial p}(1,q,z)}{\text{coefficient of }q^{j}z^{n}\text{ in }T_{k}(1,q,z)}.
\]
\bigskip
Thus, we wish to find an explicit formula for $\frac{\partial T_{k}}{
\partial p}(1,q,z)$. Differentiating equations (1) and (2), respectively,
\bigskip
\begin{align}
\frac{\partial U_{k+1}}{\partial
p}(1,q,z)&=2(T_{k}(1,q,zq)-1)+\frac{\partial T_{k}}{\partial
p}(1,q,zq), \tag{18}\\
\frac{\partial T_{k}}{\partial p}(1,q,z)&=\frac{\frac{\partial
U_{k}}{\partial p}(1,q,z)}{(1-zU_{k}(1,q,z))^{2}}. \tag{19}
\end{align}
\bigskip
Thus, after substituting equations (16) and (17), we have a recurrence.
Arbitrarily decide that
\bigskip
\begin{equation}
\frac{\partial T_{k}}{\partial p}(1,q,z)=\frac{2(A_{k}(q)-zqB_{k}(q))zq}{(1-q-z(1-q^{k+1})^{2}}. \tag{20}
\end{equation}
\bigskip
Then, using equation (18) and then (19),
\bigskip
\[
\begin{tabular}{l}
$\frac{\partial U_{k+1}}{\partial p}(1,q,z)=\frac{2zq(1-q^{k+1})}{
1-q-zq(1-q^{k+1})}+\frac{2(A_{k}-zq^{2}B_{k})zq^{2}}{
(1-q-zq(1-q^{k+1}))^{2}}$\\
\bigskip\\
$=\frac{2zq(1-q^{k+1})(1-q-zq(1-q^{k+1}))+2(A_{k}-zq^{2}B_{k})zq^{2}}{
(1-q-zq(1-q^{k+1}))^{2}},$\\
\bigskip\\
$\frac{\partial T_{k+1}}{\partial p}(1,q,z)=\frac{\frac{\partial
U_{k+1}}{
\partial p}(1,q,z)}{(\frac{1-q-z(1-q^{k+2})}{1-q-z(q-q^{k+2})})^{2}}$\\
\bigskip\\
$=\frac{2zq(
1-q^{k+1})(1-q-zq(1-q^{k+1}))+2(A_{k}-zq^{2}B_{k})zq^{2}}{(1-z(
1-q^{k+2}))^{2}}.$
\end{tabular}
\]
\bigskip
Thus, we see that
\bigskip
\begin{align}
A_{k}&=qA_{k-1}+(1-q^{k})(1-q), \nonumber\\
B_{k}&=q^{2}B_{k-1}+(1-q^{k})^{2} \nonumber.
\end{align}
\bigskip
Also, we know that $A_{0}=B_{0}=0$, since $T_{0}=\frac{1}{1-z}$. This gives
us two fairly manageable recurrences. Doing the standard analysis, it turns
out that
\bigskip
\begin{align}
A_{k}&=1-(1+k-kq)q^{k}, \nonumber\\
B_{k}&=\frac{1-2(1+q)q^{k}+(1+k+2q-kq^{2})q^{2k}}{1-q^{2}}.
\nonumber
\end{align}
\bigskip
Then, we can substitute these back into equation (20) and be generally happy.
\bigskip
So, I have some other results, but they're fairly easily derived from these
by setting $q=1$ or setting $z=1$ in $U_{k}$ or letting $k\rightarrow \infty
$, etc. It is possible to throw in some other statistics, such as the number
and sum of peaks and valleys in the words, by altering the initial condition
(3) and the recurrences (1) and (2) ever so slightly, but I never got around
to doing computations with these statistics because I was busy thinking
about other things. We did some stuff with counting the occurrences of each
number and so forth, but that more involves Dr. Rawlings's theory of
adjacencies and is going to be written up in a separate article. Also, Dr.
Lawrence Sze came up with a way to relate ascent variation with the
variation that I have defined above, so I shall include his argument as a
closing thought on this discussion. Thank you.
\bigskip
Given the same $\sigma $ as before, define the ascent variation and descent
variation:
\bigskip
\begin{equation}
avar(\sigma )=\sum_{i=1}^{n-1}\{\sigma _{i+1}-\sigma
_{i}|\sigma _{i+1}\geq \sigma
_{i}\}=\sum_{i=1}^{n-1}\frac{|\sigma _{i+1}-\sigma
_{i}|+\sigma _{i+1}-\sigma _{i}}{2}=\frac{var(\sigma )}{2}-\sigma
_{1}, \end{equation}
\begin{equation}
dvar(\sigma )=\sum_{i=1}^{n-1}\{\sigma _{i}-\sigma
_{i+1}|\sigma _{i+1}\leq \sigma
_{i}\}=\sum_{i=1}^{n-1}\frac{|\sigma _{i+1}-\sigma
_{i}|-\sigma _{i+1}+\sigma _{i}}{2}=\frac{var(\sigma )}{2}-\sigma
_{n},
\end{equation}
\bigskip
provided that we assume $\sigma _{i}\geq 0$ for the last equalities. Also,
before I get too far, define the generating functions $AT_{k}$ and $AU_{k}$
to be analogous to $T_{k}$ and $U_{k}$, with the exception that the exponent
on $p$ is $2avar(\sigma )$. Now, consider $T_{k}-T_{k-1}$ or $%
U_{k}-U_{k-1}$. Then, we have subtracted the terms for all words that do not
contain at least one $k$. Thus, these generating functions describe the
total variation for words that contain at least one $k$, under the previous
restrictions. Now, consider one such $\sigma $. Separate it into two words
at the last occurrence of $k$ in $\sigma $, calling $\sigma ^{\prime }$ the
word before and including it and $\sigma ^{\prime \prime }$ the word after
and including it. We wish to be able to compute the total variation in terms
of the ascent and descent variations. From above, we see that
\bigskip
\begin{align}
var(\sigma ^{\prime })&=2dvar(\sigma ^{\prime })+2k, \nonumber\\
var(\sigma ^{\prime \prime })&=2avar(\sigma ^{\prime \prime
})+2k. \nonumber
\end{align}
Therefore, since we have counted $k$ two extra times,
\bigskip
\[
var(\sigma )=var(\sigma ^{\prime })+var(\sigma ^{\prime \prime
})-2k=2dvar(\sigma ^{\prime })+2avar(\sigma ^{\prime \prime })+2k\text{.}
\]
\bigskip
Now, there are a few things to note. First, there is the fact that the selected $k$ does not contribute to $dvar(\sigma ^{\prime })$ or to $avar(\sigma ^{\prime \prime })$. Thus, we can remove it from each word for the remainder of the analysis. Next, note that $AT_{k}$ and $AU_{k}$ would be the same if they used $2dvar(\sigma )$ for the exponent on $p$, since $avar(\sigma )=dvar(\sigma ^{\ast })$, where $\sigma ^{\ast }$ is the reverse of $\sigma $. Also note that $\sigma ^{\prime }$ and $\sigma ^{\prime \prime }$ now come from $AT_{k}$ and $AT_{k-1}$, respectively. Finally, $n=n^{\prime }+n^{\prime \prime }+1$ and $\sum_{l=1}^{n} \sigma _{l}=\sum_{l^{\prime }=1}^{n^{\prime }}\sigma _{l^{\prime }}^{\prime }+\sum_{l^{\prime \prime }=1}^{n^{\prime \prime }}\sigma
_{l^{\prime \prime }}^{\prime \prime }+k$. Thus,
\bigskip
\begin{align}
T_{k}-T_{k-1}&=AT_{k}\ast zq^{k}\ast AT_{k-1}\ast p^{2k}, \nonumber\\
U_{k}-U_{k-1}&=AU_{k}\ast zq^{k}\ast AU_{k-1}\ast p^{2k}.
\nonumber
\end{align}
\bigskip
Since we have formulas for $T_{k}$ and $U_{k}$, we can find formulas based
on these relationships for $AT_{k}$ and $AU_{k}$, given the appropriate
initial conditions, which I trust you to figure out.
\end{document}