
\documentclass{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=4.00.0.2321}
%TCIDATA{Created=Sunday, September 07, 2003 19:38:35}
%TCIDATA{LastRevised=Sunday, September 07, 2003 19:50:49}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Standard LaTeX\Blank - Standard LaTeX Article">}
%TCIDATA{CSTFile=40 LaTeX article.cst}

\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\input{tcilatex}

\begin{document}


\begin{center}
{\large \textbf{Moment Generating Functions for Adjacency Statistics}}%
\footnote{%
Based on work supported by the National Science Foundation under Grant No.
0097392.}\\[0pt]
Don Rawlings, Lawrence Sze, and Mark Tiefenbruck \\[0pt]
Math Department, California Polytechnic State University \\[0pt]
San Luis Obispo, Ca. 93407
\end{center}

\noindent \hspace{.38in}\textbf{Key words} adjacency, variation, oscillation

\section{Introduction}

For integers $m,n\geq 1$, let $[m]^{n}$ denote the set of sequences $%
w=x_{1}x_{2}\ldots x_{n}$ of length $n$ with each $x_{i}\in \{1,2,\ldots ,m\}
$. For a real-valued function $f$ on $[m]^{2}$, the $f$-\emph{adjacency
number} of $w=x_{1}x_{2}\ldots x_{n}\in \lbrack m]^{n}$ is defined to be 
\[
\limfunc{adf}w=\sum_{k=1}^{n-1}f(x_{k}x_{k+1}).
\]%
Some specializations of the $f$-adjacency number have been considered
elsewhere. For instance, if $f(xy)$ is 1 when $x<y$ and 0 otherwise, then $%
\limfunc{adf}w$ is known as the \emph{rise number} of $w$ \cite{C,DB,FR}.
When $f(xy)=|y-x|$, the $f$-adjacency number of $w$ is referred to as the
variation of $w$ and denoted by $\limfunc{var}w$. In a sorting problem of
computer science, Levcopoulos and Petersson \cite{LP} introduced the related
notion of oscillation ($\limfunc{var}w-n+1$) as a measure of the
presortedness of a sequence of $n$ \emph{distinct} numbers. In \cite{R},
compositions were enumerated by their \emph{ascent variation}, the $f$%
-adjacency statistic induced by $f(xy)=y-x$ if $x<y$ and 0 otherwise. For
the case $f(xy)=h(|y-x|)$ where $h$ is a linear, convex, or concave
increasing real-valued function, Chao and Liang \cite{CL} described the
arrangements of $n$ distinct integers for which $\limfunc{adf}$achieves its
extreme values.

Our program here is to (a) deduce formulas for the factorial moment
generating functions of $\limfunc{adf}$and (b) compute the mean and variance
of $\limfunc{var}$on several classical combinatorial sequences. Besides the
the bounded sequences $[m]^{n}$ of length $n$, we also consider the
permutation set $S_{n}$ of $\{1,2,\ldots ,n\}$, the set of rearrangements 
\[
R_{n}(i_{1},i_{2},\ldots ,i_{m})=\{w\in \lbrack m]^{n}:l\mathrm{%
\;occurs\;exactly\;}i_{l}\;\mathrm{times\;in\;}w\mathrm{\;for\;}1\leq l\leq
m\}
\]%
where $i_{1}+i_{2}+\cdots +i_{m}=n$, and the set of compositions of $m$ into 
$n$ parts 
\[
C_{n}(m)=\{x_{1}x_{2}\ldots x_{n}\in \lbrack m]^{n}:x_{1}+x_{2}+\ldots
+x_{n}=m\}.
\]%
For $m,n\geq 2$, Table 1 displays the mean and variance of $\limfunc{var}$on
these four sets. The $k^{th}$ falling factorial of $n$ is $n^{\underline{k}%
}=n(n-1)\cdots (n-k+1)$, $\vec{i}=(i_{1},i_{2},\ldots ,i_{m})$, and, for $r$
a real number, $\lfloor r\rfloor $ denotes the greatest integer less than or
equal to $r$. From \cite{CL}, the values of $\limfunc{var}$on $S_{n}$ range
from a minimum of $n-1$ to a maximum of $(n^{2}-2)/2$ for even $n\geq 2$ and 
$(n^{2}-3)/2$ for odd $n\geq 3$. 
\[
\begin{array}{|c|c|c|}
\multicolumn{3}{c}{\mathrm{\mathbf{Table\;1}}} \\*[0.2cm]\hline
\begin{array}{c}
\mathrm{Sequences}%
\end{array}
& 
\begin{array}{c}
\mathrm{Expected\;Value\;of}\limfunc{var}%
\end{array}
& 
\begin{array}{c}
\mathrm{Variance\;of\;}\limfunc{var}%
\end{array}
\\ \hline\hline
&  &  \\ 
S_{n} & \displaystyle\frac{n^{2}-1}{3} & \displaystyle\frac{(n-2)(n+1)(4n-7)%
}{90} \\ 
&  &  \\ \hline
&  &  \\ 
\;[m]^{n} & \displaystyle\frac{(n-1)(m^{2}-1)}{3m} & \displaystyle\frac{%
(m^{2}-1)(6m^{2}n+6n-7m^{2}-2)}{90m^{2}} \\ 
&  &  \\ \hline
&  &  \\ 
R_{n}(\vec{i}) & \displaystyle\frac{2}{n}\sum_{1\leq x<y\leq
m}(y-x)i_{x}i_{y} & \displaystyle\mathrm{See\;Equation}\;(12) \\ 
&  &  \\ \hline
&  &  \\ 
C_{n}(m) & \displaystyle\frac{2(n-1)}{(m-1)^{\underline{n-1}}}%
\sum_{x=1}^{\lfloor m/2\rfloor }(m-2x)^{\underline{n-1}} & \mathrm{%
See\;Equation}\;(16) \\ 
&  &  \\ \hline
\end{array}%
\]%
David and Barton \cite[ch.\ 10]{DB} present the distributions of several
statistics (some $f$-adjacency numbers, some not) primarily on permutations.

Table 1 was determined by the participants of an eight-week undergraduate
research program directed by Rawlings and Sze during the summer of 2003. In
particular, the expected value of $\limfunc{var}$on $S_{n}$ was initially
computed by Tiefenbruck and Sze. Angeles \cite{A} filled in the entries for $%
[m]^{n}$. Tiefenbruck \cite{T} further derived a generating function for
compositions with bounded parts by a close relative of $\limfunc{var}$.

Our approach is based on a formal series identity  in Fedou and Rawlings 
\cite{FR}. The formula we deduce for the factorial moment generating
function is reasonable for determining low order moments, but is cumbersome
in general.

\section{Factorial moment generating functions}

Let $[m]^{\ast }$ denote the set of sequences of $1,2,\ldots ,m$ of finite
length (including the empty sequence of length 0). Further, let $%
z_{1},z_{2},\ldots ,z_{m}$ be commuting indeterminates and, for $%
w=x_{1}x_{2}\ldots x_{n}\in \lbrack m]^{\ast }$, define $%
Z^{w}=z_{x_{1}}z_{x_{2}}\cdots z_{x_{n}}$. From the work of Fedou and
Rawlings \cite{FR}, it follows immediately that the generating function for
sequences by $\limfunc{adf}$, namely 
\[
G(p)=\sum_{w\in \lbrack m]^{\ast }}p^{\limfunc{adf}w}Z^{w},
\]%
satisfies the identity 
\[
G(p)=\frac{1}{D(p)}
\]%
where 
\[
D(p)=\displaystyle1-\displaystyle\sum_{n\geq 1}\sum_{x_{1}\ldots x_{n}\in
\lbrack m]^{n}}Z^{x_{1}\ldots x_{n}}\prod_{k=1}^{n-1}(p^{f(x_{k}x_{k+1})}-1).
\]%
Examples are presented in \cite{FR,R} for which D has a closed form. We do
not know of a closed form for D when $\limfunc{adf}=\limfunc{var}$(that is,
when $f(x,y)=|y-x|$).

To avoid the quotient and chain rule in computing the $d^{th}$  derivative
of $G$ with respect to $p$, rewrite (1) as $GD=1$.  Differentiating the
latter $d$ times, $d \geq 1$, and dividing by  $d!$ gives  
\begin{eqnarray}
\sum_{j=0}^{d} \frac{G^{(d-j)}}{(d-j)!}\frac{D^{(j)}}{j!}=0.
\end{eqnarray}
To solve for $G^{(d)}$, consider the system 
\begin{eqnarray*}
\begin{array}{cccccccccc}
\frac{G^{(d)}}{d!}\frac{D^{(0)}}{0!} & + & \frac{G^{(d-1)}}{(d-1)!}\frac{%
D^{(1)}}{1!} & + & \frac{G^{(d-2)}}{(d-2)!}\frac{D^{(2)}}{2!} & + & \cdots +
& \frac{G^{(0)}}{0!}\frac{D^{(d)}}{d!} & = & 0 \\*[.3cm] 
& + & \frac{G^{(d-1)}}{(d-1)!}\frac{D^{(0)}}{0!} & + & \frac{G^{(d-2)}}{%
(d-2)!}\frac{D^{(1)}}{1!} & + & \cdots + & \frac{G^{(0)}}{0!}\frac{D^{(d-1)}%
}{(d-1)!} & = & 0 \\ 
&  &  &  &  &  &  & \vdots &  &  \\ 
&  &  &  &  & \frac{G^{(1)}}{1!}\frac{D^{(0)}}{0!} & + & \frac{G^{(0)}}{0!}%
\frac{D^{(1)}}{1!} & = & 0 \\*[.3cm] 
&  &  &  &  &  &  & \frac{G^{(0)}}{0!}\frac{D^{(0)}}{0!} & = & 1%
\end{array}%
\end{eqnarray*}
where the top $d$ equations arise from repeated application of (3). 
Cramer's rule applied to the above system yields 
\begin{eqnarray*}
\frac{G^{(d)}}{d!}=\frac{(-1)^{d}}{D^{d+1}} \left| 
\begin{array}{cccccccc}
\frac{D^{(1)}}{1!} & \frac{D^{(2)}}{2!} & \frac{D^{(3)}}{3!} &  & \cdots & 
&  & \frac{D^{(d)}}{d!} \\*[.3cm] 
\frac{D^{(0)}}{0!} & \frac{D^{(1)}}{1!} & \frac{D^{(2)}}{2!} &  &  &  &  & 
\frac{D^{(d-1)}}{(d-1)!} \\*[.3cm] 
0 & \frac{D^{(0)}}{0!} & \frac{D^{(1)}}{1!} &  &  &  &  & \frac{D^{(d-2)}}{%
(d-2)!} \\ 
\vdots &  &  &  &  &  &  & \vdots \\*[.7cm] 
0 &  &  & \cdots &  & 0 & \frac{D^{(0)}}{0!} & \frac{D^{(1)}}{1!}%
\end{array}
\right|
\end{eqnarray*}
which, when expanded, implies  
\begin{eqnarray}
G^{(d)}=\sum_{\nu=1}^{d}\frac{(-1)^{\nu}}{D^{\nu +1}}\sum_{{\scriptsize 
\begin{array}{c}
j_{1}+\cdots +j_{\nu}=l \\ 
j_{k} \geq 1%
\end{array}%
}} {\binom{d }{j_{1} \ldots j_{\nu}}} D^{(j_1)}\cdots D^{(j_\nu)}.
\end{eqnarray}

To get at a formula for the $d^{th}$ factorial moment $G^{(d)}(1)$, first
observe that 
\[
\displaystyle D^{(j)}(1)=-\sum_{r=2}^{j+1}D_{r}^{(j)}
\]%
where 
\[
D_{r}^{(j)}=\displaystyle\sum_{x_{1}\ldots x_{r}\in \lbrack
m]^{r}}Z^{x_{1}\ldots x_{r}}\sum_{{\scriptsize 
\begin{array}{c}
l_{1}+\cdots +l_{r-1}=j \\ 
l_{k}\geq 1%
\end{array}%
}}{\binom{j}{l_{1}\ldots l_{r-1}}}\prod_{k=1}^{r-1}f(x_{k}x_{k+1})^{%
\underline{l_{k}}}\;.
\]%
For instance, 
\[
\begin{array}{l}
\displaystyle D_{2}^{\prime }=\sum_{xy\in \lbrack
m]^{2}}f(xy)z_{x}z_{y},\;\;\;\displaystyle D_{2}^{\prime \prime
}=\sum_{xy\in \lbrack m]^{2}}f(xy)^{\underline{2}}z_{x}z_{y},\;\;\;\mathrm{%
and} \\*[0.7cm]
\displaystyle D_{3}^{\prime \prime }=2\sum_{vxy\in \lbrack
m]^{3}}f(vx)f(xy)z_{v}z_{x}z_{y}.%
\end{array}%
\]%
Further setting $\vec{j}=(j_{1},\ldots ,j_{\nu })$, $||\vec{j}%
||=j_{1}+\cdots +j_{\nu }$, 
\[
{\binom{d}{\vec{j}}}={\binom{d}{j_{1}\ldots j_{\nu }}},\;\;\;\mathrm{and}%
\;\;\;D_{\mu }^{(\vec{j})}=\sum_{{\tiny 
\begin{array}{c}
r_{1}+\cdots +r_{\nu }=\mu  \\ 
r_{k}\geq 2%
\end{array}%
}}D_{r_{1}}^{(j_{1})}\cdots D_{r_{\nu }}^{(j_{\nu })},
\]%
it follows from (4) and (5) that 
\[
G^{(d)}(1)=\sum_{\nu =1}^{d}\frac{1}{D^{\nu +1}(1)}\sum_{{\scriptsize 
\begin{array}{c}
||\vec{j}||=d \\ 
j_{k}\geq 1%
\end{array}%
}}{\binom{d}{\vec{j}}}\sum_{\mu =2\nu }^{d+\nu }D_{\mu }^{(\vec{j})}.
\]%
As $D(1)=1-(z_{1}+\cdots +z_{m})$, extracting the contributions made by all $%
w\in \lbrack m]^{n}$ from both sides of (7) gives 
\[
\sum_{w\in \lbrack m]^{n}}(\limfunc{adf}w)^{\underline{d}}\,Z^{w}=\sum_{\nu
=1}^{d}\sum_{{\scriptsize 
\begin{array}{c}
||\vec{j}||=d \\ 
j_{k}\geq 1%
\end{array}%
}}{\binom{d}{\vec{j}}}\sum_{\mu =2\nu }^{d+\nu }{\binom{n+\nu -\mu }{\nu }}%
\left( \sum_{i=1}^{m}z_{i}\right) ^{n-\mu }D_{\mu }^{(\vec{j})}\;\;
\]%
valid for $d\geq 1$. When $d=1,2$, (6) and (8) imply that 
\[
\displaystyle\sum_{w\in \lbrack m]^{n}}\limfunc{adf}w\,Z^{w}=\displaystyle%
(n-1)\left( \sum_{i=1}^{m}z_{i}\right) ^{n-2}\sum_{xy\in \lbrack
m]^{2}}f(xy)z_{x}z_{y}
\]%
and that 
\[
\begin{array}{lcl}
\displaystyle\sum_{w\in \lbrack m]^{n}}(\limfunc{adf}w)^{\underline{2}%
}\,Z^{w} & = & \displaystyle(n-1)\left( \sum_{i=1}^{m}z_{i}\right)
^{n-2}\sum_{xy\in \lbrack m]^{2}}(f(xy))^{\underline{2}}z_{x}z_{y} \\*[0.5cm]
&  & +\displaystyle2(n-2)\left( \sum_{i=1}^{m}z_{i}\right)
^{n-3}\sum_{vxy\in \lbrack m]^{3}}f(vx)f(xy)z_{v}z_{x}z_{y} \\*[0.5cm]
&  & +\displaystyle(n-2)(n-3)\left( \sum_{i=1}^{m}z_{i}\right) ^{n-4}\left(
\sum_{xy\in \lbrack m]^{2}}f(xy)z_{x}z_{y}\right) ^{2}.%
\end{array}%
\]

\section{Discussion of Table 1}

The entries in Table 1 are consequences of (9) and (10) with $f(xy)=|y-x|$
and with appropriate substitutions for $Z$. For the mean and variance of $%
\limfunc{var}$on the set of bounded sequences $[m]^{n}$, put $z_{i}=1$ for $%
1\leq i\leq m$. Noting that 
\[
\sum_{xy\in \lbrack m]^{2}}|y-x|=\sum_{1\leq x<y\leq m}2(y-x)=2{\binom{m+1}{3%
}},
\]%
it follows from (9) that the mean of $\limfunc{var}$on $[m]^{n}$ is 
\[
\frac{1}{m^{n}}\sum_{w\in \lbrack m]^{n}}\limfunc{var}w=\frac{2(n-1)m^{n-2}}{%
m^{n}}{\binom{m+1}{3}}=\frac{(n-1)(m^{2}-1)}{3m}.
\]%
As 
\[
\sum_{xy\in \lbrack m]^{2}}|y-x|^{\underline{2}}=4{\binom{m+1}{4}}
\]%
and as 
\begin{eqnarray*}
\displaystyle\sum_{vxy\in \lbrack m]^{n}}|x-v||y-x| &=&\displaystyle%
\sum_{1\leq v<x<y\leq m}2(x-v)(y-x)\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;
\\
&&\ast \lbrack .7cm]+\displaystyle\sum_{1\leq x<y\leq v\leq
m}4(v-x)(y-x)-\sum_{1\leq x<y\leq m}2(y-x)^{2} \\
\ast \lbrack .7cm] &=&\displaystyle\frac{7m^{2}-8}{10}{\binom{m+1}{3}},\;\;\;
\end{eqnarray*}%
(10) implies that 
\begin{eqnarray*}
\frac{1}{m^{n}}\sum_{w\in \lbrack m]^{n}}(\limfunc{var}w)^{\underline{2}} &=&%
\frac{4(n-1)}{m^{2}}{\binom{m+1}{4}}+\frac{(n-2)(7m^{2}-8)}{5m^{3}}{\binom{%
m+1}{3}} \\
&&\ast \lbrack .5cm]+\frac{4(n-2)(n-3)}{m^{4}}{\binom{m+1}{3}}^{2}.
\end{eqnarray*}%
Then, subbing the last result into 
\[
\frac{1}{m^{n}}\sum_{w\in \lbrack m]^{n}}(\limfunc{var}w)^{\underline{2}}+%
\frac{(n-1)(m^{2}-1)}{3m}-\left( \frac{(n-1)(m^{2}-1)}{3m}\right) ^{2}
\]%
and simplifying gives the variance of $\limfunc{var}$as recorded in Table 1.

For $R_{n}(\vec{i})$, extracting the coefficient of $%
z_{1}^{i_{1}}z_{2}^{i_{2}}\cdots z_{m}^{i_{m}}$ from (9) leads to 
\[
\displaystyle\sum_{w\in R_{n}(\vec{i})}\limfunc{var}w=\displaystyle%
2(n-1)\sum_{1\leq x<y\leq m}(y-x){\binom{n-2}{i_{1}\ldots i_{x}-1\ldots
i_{y}-1\ldots i_{m}}}
\]%
and then dividing by the cardinality of $R_{n}(\vec{i})$ gives the mean of $%
\limfunc{var}$as 
\[
{\binom{n}{\vec{i}}}^{-1}\sum_{w\in R_{n}(\vec{i})}\limfunc{var}w=%
\displaystyle\frac{2}{n}\sum_{1\leq x<y\leq m}(y-x)i_{x}i_{y}.
\]%
Let $\vec{i}_{\setminus r}=(i_{1},\ldots ,i_{r}-1,\ldots ,i_{n})$. For
example, $(3,2,1,4)_{\setminus 3\setminus 2\setminus 3}=(3,1,-1,4)$. The
variance on $R_{n}(\vec{i})$ is then 
\[
{\binom{n}{\vec{i}}}^{-1}\sum_{w\in R_{n}(\vec{i})}\limfunc{var}w^{%
\underline{2}}+\frac{2}{n}\sum_{1\leq x<y\leq m}(y-x)i_{x}i_{y}-\left( %
\displaystyle\frac{2}{n}\sum_{1\leq x<y\leq m}(y-x)i_{x}i_{y}\right) ^{2}\;\;
\]%
where, upon extraction of the coefficient of $z_{1}^{i_{1}}z_{2}^{i_{2}}%
\cdots z_{m}^{i_{m}}$ from (10), we have 
\[
\begin{array}{r}
\displaystyle\sum_{w\in R_{n}(\vec{i})}(\limfunc{var}w)^{\underline{2}}=%
\displaystyle(n-1)\sum_{1\leq x,y\leq m}|y-x|^{\underline{2}}{\binom{n-2}{%
\vec{i}_{\setminus x\setminus y}}}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \\%
*[0.5cm]
+\displaystyle2(n-2)\sum_{1\leq v,x,y\leq m}|x-v||y-x|{\binom{n-3}{\vec{i}%
_{\setminus v\setminus x\setminus y}}}\;\;\;\;\; \\*[0.5cm]
+\displaystyle(n-2)(n-3)\sum_{1\leq u,v,x,y\leq m}|v-u||y-x|{\binom{n-4}{%
\vec{i}_{\setminus u\setminus v\setminus x\setminus y}}}.%
\end{array}%
\]

The permutation entries follow from (11) and (12). Selecting $m=n$ and $%
i_{k}=1$ for $1\leq k\leq n$ in (11) reveals the mean of $\limfunc{var}$on $%
S_{n}$ as 
\[
\frac{1}{n!}\sum_{w\in S_{n}}\limfunc{var}w=\displaystyle\frac{2}{n}%
\sum_{1\leq x<y\leq n}(y-x)=\frac{2}{n}{\binom{n+1}{3}}=\frac{n^{2}-1}{3}.
\]%
From (13) with $m=n$ and $i_{k}=1$ for $1\leq k\leq n$, 
\[
\begin{array}{lcl}
\displaystyle\sum_{w\in S_{n}}(\limfunc{var}w)^{\underline{2}} & = & %
\displaystyle(n-1)!\sum_{1\leq x,y\leq n}|y-x|^{\underline{2}} \\*[0.7cm]
\displaystyle &  & +\displaystyle2(n-2)!\sum_{1\leq v,x,y\leq n}|x-v||y-x| \\%
*[0.7cm]
&  & +\displaystyle(n-2)!\sum_{{\scriptsize 
\begin{array}{c}
1\leq u,v,x,y\leq m \\ 
\{u,v\}\cap \{x,y\}=\emptyset 
\end{array}%
}}|v-u||y-x| \\*[0.7cm]
& = & \displaystyle(4/15)(n-2)!(10n^{2}+14n-27){\binom{n+1}{4}}.%
\end{array}%
\]%
So the variance of $\limfunc{var}$on $S_{n}$ is 
\[
\frac{1}{n!}\sum_{w\in S_{n}}\limfunc{var}w^{\underline{2}}+\frac{n^{2}-1}{3}%
-\left( \frac{n^{2}-1}{3}\right) ^{2}=\frac{(n-2)(n+1)(4n-7)}{90}.
\]

For $w=x_{1}\ldots x_{n}\in \lbrack m]^{n}$, let $||w||=x_{1}+\cdots +x_{n}$%
. For the composition results in Table 1, set $z_{k}=q^{k}$ for $1\leq k\leq
m$. Then (9) becomes 
\[
\displaystyle\sum_{w\in \lbrack m]^{n}}\limfunc{var}w\,q^{||w||}=%
\displaystyle(n-1)q^{n-2}\left( \frac{1-q^{m}}{1-q}\right) ^{n-2}\sum_{1\leq
x,y\leq m}|y-x|q^{x+y}
\]%
and (10) implies that 
\[
\begin{array}{r}
\displaystyle\sum_{w\in \lbrack m]^{n}}(\limfunc{var}w)^{\underline{2}%
}\,q^{||w||}=\displaystyle(n-1)q^{n-2}\left( \frac{1-q^{m}}{1-q}\right)
^{n-2}\sum_{1\leq x,y\leq m}|y-x|^{\underline{2}}q^{x+y}\;\;\;\;\;\;\;\; \\%
*[0.5cm]
+\displaystyle2(n-2)q^{n-3}\left( \frac{1-q^{m}}{1-q}\right)
^{n-3}\sum_{1\leq v,x,y\leq m}|x-v||y-x|q^{v+x+y}\;\;\;\; \\*[0.5cm]
+\displaystyle(n-2)(n-3)q^{n-4}\left( \frac{1-q^{m}}{1-q}\right)
^{n-4}\sum_{1\leq u,v,x,y\leq m}|v-u||y-x|q^{u+v+x+y}.%
\end{array}%
\]%
Extracting the coefficient of $q^{m}$ from (14) to obtain 
\[
\begin{array}{lcl}
\displaystyle\sum_{w\in C_{n}(m)}\limfunc{var}w & = & \displaystyle%
2(n-1)\sum_{1\leq x<y\leq m}(y-x){\binom{m-1-x-y}{n-3}} \\*[0.5cm]
& = & \displaystyle2(n-1)\sum_{1\leq x\leq \lfloor m/2\rfloor }{\binom{m-2x}{%
n-1}}%
\end{array}%
\]%
and then dividing by the cardinality ${\binom{m-1}{n-1}}$ of $C_{n}(m)$
gives the mean of $\limfunc{var}$as stated in Table 1. The variance is 
\[
\begin{array}{r}
\displaystyle{\binom{m-1}{n-1}}^{-1}\sum_{w\in C_{n}(m)}\limfunc{var}w^{%
\underline{2}}+\frac{2(n-1)}{(m-1)^{\underline{n-1}}}\sum_{1\leq x\leq
\lfloor m/2\rfloor }(m-2x)^{\underline{n-1}} \\*[0.5cm]
-\displaystyle\left( \frac{2(n-1)}{(m-1)^{\underline{n-1}}}\sum_{1\leq x\leq
\lfloor m/2\rfloor }(m-2x)^{\underline{n-1}}\right) ^{2}%
\end{array}%
\]%
where, pulling the coefficient of $q^{m}$ from (15), we have 
\[
\begin{array}{r}
\displaystyle\sum_{w\in C_{n}(m)}(\limfunc{var}w)^{\underline{2}}=%
\displaystyle(n-1)\sum_{1\leq x,y\leq m}|y-x|^{\underline{2}}{\binom{m-1-x-y%
}{n-3}}\;\;\;\;\;\;\;\;\;\; \\*[0.5cm]
+\displaystyle2(n-2)\sum_{1\leq v,x,y\leq m}|x-v||y-x|{\binom{m-1-v-x-y}{n-4}%
}\;\;\;\;\; \\*[0.5cm]
+\displaystyle(n-2)(n-3)\sum_{1\leq u,v,x,y\leq m}|v-u||y-x|{\binom{%
m-1-u-v-x-y}{n-5}}.%
\end{array}%
\]%
The sums in (17) simplify somewhat. For instance, 
\[
\sum_{1\leq x,y\leq m}|y-x|^{\underline{2}}{\binom{m-1-x-y}{n-3}}%
=4\sum_{1\leq x\leq \lfloor m/2\rfloor }{\binom{m-2x}{n}}.
\]%
As a part of the second sum on the righthand side of (18), we note that 
\[
\begin{array}{r}
\displaystyle\sum_{1\leq x\leq v<y\leq m}(v-x)(y-x){\binom{m-1-v-x-y}{n-4}}%
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;%
\;\;\;\;\; \\*[0.5cm]
\displaystyle=\frac{1}{n(n-1)}\sum_{1\leq v\leq m-1}A_{m,n,v}{\binom{m-1-3v}{%
n-2}}+B_{m,n,v}{\binom{m-2v-1}{n-2}}%
\end{array}%
\]%
where $A_{m,n,v}=3v-3vn-m+mn-9v^{2}+6vm-m^{2}+v^{2}n-v^{2}m$ and $%
B_{m,n,v}=m-2v+2vn-mn+4v^{2}-4vm+m^{2}+v^{2}n-vnm+v^{2}n^{2}$. The four-fold
summations arising in the final sum of (18) reduce to double sums. \\*[0.5cm]
\noindent \textbf{Acknowledgement} We thank Michele Valiquette for bringing
Chao and Liang's work \cite{CL} to our attention. 

\begin{thebibliography}{9}
\bibitem{A} Rudolpho Angeles, The mean and variance of variation  statistics
on bounded sequences, . 

\bibitem{C} L.\ Carlitz, Enumeration of compositions by rises,  falls, and
levels, \emph{Math.\ Nachrichtne} \textbf{77} (1977) 361-371.

\bibitem{CL} C-C.\ Chao and W-Q.\ Liang, Arranging $n$ distinct numbers on a
line or a circle to reach extreme total variations, \emph{Europ.\ J.\ Combin.%
} \textbf{13} (1992) 325-334.

\bibitem{DB} F.\ N.\ David and D.\ E.\ Barton, \emph{Combinatorial Chance},
Hafner Publ.\ Company, 1962.

\bibitem{FR} J.\ M.\ Fedou and D.\ P.\ Rawlings, Adjacencies in words, \emph{%
Adv.\ Appl.\ Math.} \textbf{16} (1995) 206-218.

\bibitem{LP} C.\ Levcopoulos and O.\ Petersson, Heapsort-adapted for
presorted files, \emph{Lecture Notes in Computer Science} \textbf{382}
(1989) 499-509.

\bibitem{R} D.\ P.\ Rawlings, Restricted words by adjacencies, \emph{%
Discrete Math.} \textbf{220} (2000) 183-200.

\bibitem{T} M.\ Tiefenbruck, Enumerating compositions with bounded parts by
variation, .
\end{thebibliography}

\end{document}
