\documentclass{tournam}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage[active]{srcltx} % SRC Specials for DVI Searching

%First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire
%--needed to be modified, because of personal style file tournam.cls.
%--The headline is put into tournam.cls!
%\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8
%\markright{\its S\'eminaire Lotharingien de
%Combinatoire \bfs 47 \rms (2002), Article~B47h\hfill}
%\def\thepage{}
%


\def\S{\mathcal{S}}
\def\T{\mathcal{T}}
\def\O{\mathcal{O}}
\def\I{\mathcal{I}}
\def\J{\mathcal{J}}
\def\B{\mathcal{B}}
\def\V{\mathcal{V}}
\def\F{\mathcal{F}}
\def\C{\mathcal{C}}
\def\U{\mathbf{U}}
\def\V{\mathbf{V}}
\def\Wbar{\overline{W}}



\newcommand{\myqed}{\hspace*{\fill}\qed}


\begin{document}
\begin{frontmatter}
\title{Computing Tournament Sequence Numbers \\efficiently \\
with Matrix Techniques}
\author{Erich Neuwirth}
\makeatletter
\address{Department of Statistics and Decision Support Systems \\
University of Vienna \\
{\tt erich.neuwirth@univie.ac.at} } \makeatother

\begin{abstract}
We give a new, ``almost explicit'' formula for tournament
numbers, representing them as upper left elements of the
$n^\text{th}$ power of a matrix with an explicit formula for
elements of the original matrix. Using this representation, we
show how to compute tournament numbers in time complexity
$O(n^6)$. \\
%The technique we use can also be adapted for other ``well
%behaved'' counting problems.
\end{abstract}
\end{frontmatter}


\section{Main results}

Tournament sequences are defined as sequences $(t_1,t_2,....)$
with $t_1=1$ and $t_i<t_{i+1}\leq 2 t_i$. Defining $T_k$-sequences
as sequences with $(t_1,t_2,....)$ with $t_1=k$ and
$t_i<t_{i+1}\leq 2 t_i$ we see that tournament sequences are
$T_1$-sequences. Now let $T(n,k)$ denote the number of
$T_k$-sequences of length $n$. It is obvious that $T(1,k)=1$ for
all $k$. To compute $T(n,k)$ for $n>1$ we note that
$T_k$-sequences of length $n$ are produced by taking $t_1=k$, and
appending all $T_i$-sequences of length $n-1$ which are
``admissible'' extensions of a sequence starting with $k$. It is
obvious that $k+1\leq i \leq 2k$ are the only possible choices for
the first element of the extension sequence. Therefore, we have
the recursion
\begin{equation}\label{eqn:Trecur}
T(n,k)=\sum_{j=k+1}^{2k}{T(n-1,j)}.
\end{equation}

We call $T$ the tournament matrix.

The tournament numbers we want to compute are $T(n)=T(n,1)$, and
$T(n)$ is the number of tournament sequences of length $n$.\\
The values for $T(n)$ for $n=1,2,\ldots 16$ are \\
1, 1, 2, 7, 41, 397, 6377, 171886, 7892642, 627340987, 87635138366,\\
21808110976027, 9780286524758582, 7981750158298108606,\\
11950197013167283686587, 33046443615914736611839942.

Capelli and Narayana introduced tournament sequences in
\cite{narayanapap}. Further results about $T(n)$ can be found in
Sloane's On-Line Encyclopedia of Integer Sequences \cite{sloanenc}
(sequence A008934). Tournament numbers have been studied by
Torelli (see \cite{torellirep}) in connection with the Goldbach
conjecture. Kleber and Cook studied algorithmic aspects of
computing $T(n)$ extensively in \cite{klebercookpap}. They showed
that $T(n)$ can be computed in time complexity $O(n^6)$ by
transforming the original recursive equations, which by themselves
would lead to exponential time complexity.

In this paper, we present an ``almost explicit'' formula for
computing $T(n)$, and we show that this formula computes
$T(n)$ with time complexity $O(n^6)$, similar to the  Kleber-Cook
results. We then discuss why for practical purposes our
method works noticeably faster than their method.

Here are our two main results.

\begin{thm}
\label{thm:matrixrep} Let $n\geq 2$. Then $T(n)$ is the upper left
element of the matrix power $C_{n-1}^{n-1}$ where $C_{m}$ is
the $m \times m$-matrix with elements\\
%\begin{align}
%\begin{equation}
%\begin{split}
\begin{equation}
\label{eqn:Cdef}
\begin{array}{lcl}
C(i,j)&=&2^{2i-j-2}\bigl(\binom{i-1}{j-i+1}+ 4 \binom{i-1}{j-i} +
%\\ & & %
4\binom{i-1}{j-i-1}\bigr), \\  &&\text{ for } i\neq j \text{ and }
i - 1
\neq j ; \\
C(i+1,i)&=&2^i-1 ; \\
C(i,i)&=&2^{i-2}(i+3)-1;
\end{array}
\end{equation}
\\
for $1 \leq i$, $j \leq m$.
%\end{align}
%\end{split}
\end{thm}

Here are the first few lines and columns of this matrix:
\begin{equation*}
\begin{pmatrix}
   \makebox[8mm][c]{1} & \makebox[8mm][c]{1} & \makebox[8mm][c]{0} & \makebox[8mm][c]{0}
   & \makebox[8mm][c]{0} & \makebox[8mm][c]{0} & \makebox[8mm][c]{0} &\ldots \\
   1 & 4 & 4 & 1 & 0 & 0 & 0 &\ldots \\
   0 & 3 & 11 & 13 & 6 & 1 & 0 &\ldots \\
   0 & 0 & 7 & 27 & 38 & 25 & 8 &\ldots \\
   0 & 0 & 0 & 15 & 63 & 104 & 88 &\ldots \\
   0 & 0 & 0 & 0 & 31 & 143 & 272 &\ldots \\
   0 & 0 & 0 & 0 & 0 & 63 & 319 &\ldots \\
%   999 & 999 & 999 & 999 & 999 & 999 & 999 &\ldots \\
   \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots &\ddots
\end{pmatrix}
\end{equation*}



\begin{thm}
\label{thm:complexity} Using the representation of Theorem
\ref{thm:matrixrep}, $T(n)$ can be computed in time complexity
$O(n^6)$.
\end{thm}


\section{Matrix preliminaries}

The key for applying matrix techniques to our problem is the
observation that Equation (\ref{eqn:Trecur}) can be interpreted in
the
following way:\\
Let $\U$ be the matrix with elements $T(i,j)$, $i\geq 1$, $j\geq
1$. Then each row of $\U$ can be obtained by multiplying the
previous row with the matrix $W$ from the right, where $W$ has the
elements $W(i,j)=1$ for $j<i\leq 2j$ and $W(i,j)=0$ everywhere
else. Writing the matrices $\U$ and $W$ elementwise, we have

{\tiny
\begin{equation*}
\left(
\begin{array}{cccccc}
T(2,1) & T(2,2) & T(2,3) & T(2,4)& T(2,5)& \ldots \\
T(3,1) & T(3,2) & T(3,3) & T(3,4)& T(3,5)& \ldots \\
T(4,1) & T(4,2) & T(4,3) & T(4,4)& T(4,5)& \ldots \\
T(5,1) & T(5,2) & T(5,3) & T(5,4)& T(5,5)& \ldots \\
T(6,1) & T(6,2) & T(6,3) & T(6,4)& T(6,5)& \ldots \\
\vdots & \vdots &\vdots &\vdots &\vdots  & \ddots
\end{array}
\right) = \left(
\begin{array}{cccccc}
T(1,1) & T(1,2) & T(1,3) & T(1,4)& T(1,5)& \ldots \\
T(2,1) & T(2,2) & T(2,3) & T(2,4)& T(2,5)& \ldots \\
T(3,1) & T(3,2) & T(3,3) & T(3,4)& T(3,5)& \ldots \\
T(4,1) & T(4,2) & T(4,3) & T(4,4)& T(4,5)& \ldots \\
T(5,1) & T(5,2) & T(5,3) & T(5,4)& T(5,5)& \ldots \\
\vdots & \vdots &\vdots &\vdots &\vdots  & \ddots
\end{array}
\right)
\left(
\begin{array}{cccccc}
0 & 0 & 0 & 0 & 0 & \ldots \\
1 & 0 & 0 & 0 &0 & \ldots \\
0 & 1 & 0 & 0 & 0 & \ldots \\
0 & 1 & 1 & 0 & 0 & \ldots \\
0 & 0 & 1 & 0 & 0 & \ldots \\
\vdots & \vdots &\vdots &\vdots &\vdots  & \ddots
\end{array}
\right)
\end{equation*}
}

$\U$ and $W$ are infinite matrices, and for infinite matrices
multiplication is not always well defined. Matrix multiplication
for infinite matrices is, however, well defined, if either all the
rows of the left factor have only finitely many nonzero elements,
or if  all the columns of the right factor have only finitely many
nonzero elements. We call a matrix with rows with only
finitely many nonzero elements a {\em matrix with finite rows},
and we call a matrix with columns with only finitely many
nonzero elements a {\em matrix with finite columns}.

In our case, matrix $W$ has finite rows and finite columns, and
therefore rewriting recursion (\ref{eqn:Trecur}) as matrix
equation is possible. Furthermore, any infinite matrix can be
multiplied with $W$ from the left and from the right.

\label{sec:matprelim} In the rest of this paper, we will use
matrix techniques for operations on recursively defined functions.
These techniques have been pioneered by Kemeny in \cite{kemenypap}
and extensively used by Neuwirth in \cite{neuwirthgaltonpap}.


For our proof, we will need some ``helper matrices''. We will use
infinite matrices. \\
 All our matrices start with row 1
and column 1. \\
$\delta_{i,j}$ is the standard Kronecker symbol, defined by
$\delta_{i,i}=1$ and $\delta_{i,j}=0$ for$i\neq j$.
\\
$\I$ defined by $\I(n,k)=\delta_{n,k}$ is the identity matrix.
\\
$\S$ defined by $\S(n,k)=\delta_{n+1,k}$ is a matrix with $1$s
just above the main diagonal and $0$s everywhere else. \\
$\T$ defined by $\T(n,k)=\delta_{n,k+1}$ is a matrix with $1$s
just below the main diagonal and $0$s everywhere else. \\
$\O_n$ defined by $\O_n(m,k)= \delta_{m,k}$ for $m\leq n$ and
$\O_n(m,k)= 0$ for $m>n$ is a ``cut off'' identity matrix. \\
$\J$ defined by $\J(n,k)=1$ for $n\geq k$ and $\J(n,k)=0$ for $n <
k$ is a lower triangular matrix with $1$s everywhere on and below
the main diagonal. \\
 $\B$ defined by $\B(n,k)=\binom{n-1}{k-1}$ is the triangular
matrix consisting of the binomial coefficients.\\
We note that with the exception of $\S$ all these matrices are
lower triangular.\\
$M'$ denotes the transpose of $M$ for any matrix $M$.\\
We will need the following identities for these matrices:

\begin{equation}
\label{eqn:ST}
\S \T = \I
\end{equation}
\begin{equation}
(\I-\T)^{-1}=\J
\end{equation}

For a (lower) triangular matrix $D$ we have

\begin{equation}
\label{eqn:Ocut} \O_n D= \O_n D \O_n
\end{equation}
Furthermore we also have\\
\begin{equation}
\label{eqn:Ocanc} \O_n \O_m= \O_{\min(m,n)}
\end{equation}
\begin{equation}
\label{eqn:OS} \O_n \S^k= \S^k \O_{n+k}
\end{equation}
and
\begin{equation}
\J \B = (\I-\T)^{-1}\B= \S \B \T
\end{equation}

The last equation is just ``the matrix way'' of rewriting
$\sum_{i=0}^{n}{\binom{i}{k}}=\binom{n+1}{k+1}$.

$\overline{\B}=\B^{-1}$, the inverse of $\B$, has the elements
$\overline{\B}(n,k)=\binom{n-1}{k-1}(-1)^{n+k}$, so it may be
described as ``the binomials with a checkerboard sign pattern''.

For a triangular matrix $D$ the matrix $\O_n D \O_n$ is the ``left
upper $n \times n$-block'' of the matrix. To compute the upper
left block of the power of a triangular matrix, we only need the
block of the same size of the original matrix. Translated into our
matrix techniques, this becomes the following lemma:

\begin{lem}
\label{lem:Ocut} Let $D$ be triangular. Then $\O_n D^k \O_n =
(\O_n D \O_n)^k$.
\end{lem}
\begin{pf}
This is an immediate consequence of Equation (\ref{eqn:Ocut}).
\myqed
\end{pf}
The situation becomes more complicated when we allow matrices with
some diagonals above the main diagonal having nonzero elements. We
will study a special class of matrices.

\begin{defn}
A matrix $M$ is called $d$-supertriangular if $M(n,k)=0$ for \\
$k>n+d$.
\end{defn}

\begin{lem}
\label{lem:superchar} $M$ is $d$-supertriangular iff there exists
a triangular matrix $D$ with $M=S^d D$.
\end{lem}
\begin{pf}
Trivial.\myqed
\end{pf}

\begin{lem}
\label{lem:supercut} For a $d$-supertriangular matrix $M$ we have
$\O_n M=\O_n M \O_{n+d}$.
\end{lem}
\begin{pf}
According to Lemma \ref{lem:superchar} we have $M=\S^d D$ with a
triangular matrix $D$. \\
Therefore, using Equation (\ref{eqn:OS}) we have $\O_n M=\O_n S^d D=S^d \O_{n+d} D$. \\
Using Equation (\ref{eqn:Ocut}) we have $S^d \O_{n+d} D= S^d
\O_{n+d} D
\O_{n+d}$. \\
Using Equation (\ref{eqn:OS}) again we have  $S^d \O_{n+d}
D\O_{n+d} = \O_{n} \S^d D \O_{n+d}=\O_{n} M \O_{n+d}$.
 \myqed
\end{pf}

\begin{lem}\label{lem:superdpower}
For a $d$-supertriangular matrix $M$ we have \\
$\O_n M^k \O_n=\O_n(\O_{n+(k-1)d} M \O_{n+(k-1)d})^k\O_n$.
\end{lem}
\begin{pf}
Using Lemma \ref{lem:supercut} we have\\
$\O_n M^k \O_n=\O_n M M^{k-1} \O_n=\O_n M \O_{n+d} M^{k-1}
\O_n$.\\
Applying Lemma \ref{lem:supercut} repeatedly from left to right
following this
pattern we have \\
$\O_n M^k \O_n=\O_n M \O_{n+d}M  \O_{n+2d} M\O_{n+3d}\cdots \O_{n+(k-1)d}M \O_{n+kd}\O_n$.\\
Replacing the terms $\O_{n+id}$ by
$\O_{n+(k-1)d}\O_{n+id}\O_{n+(k-1)d}$ for $i\leq k-1$ and
replacing the last term $\O_n$ by $\O_{n+(k-1)d)} \O_n$ we have
\\
$
\O_n M^k \O_n=\O_n \O_{n+(k-1)d}M\O_{n+(k-1)d}
\O_{n+d}\\
\text{\qquad\qquad\quad}\;\;\cdot\O_{n+(k-1)d}M\O_{n+(k-1)d} \O_{n+2d}\\
\text{\qquad\qquad\quad}\;\;\cdot\O_{n+(k-1)d}
M\O_{n+(k-1)d}\O_{n+3d}\cdots\\
\text{\qquad\qquad\quad}\;\;\cdot\O_{n+(k-1)d}M \O_{n+kd}\O_{n+(k-1)d}\O_n
$
\\
Since $\overline{M}=\O_{n+(k-1)d}M \O_{n+(k-1)d}$ is $d$-supertriangular
and  \\
$\O_{n+kd}\O_{n+(k-1)d} =\O_{n+(k-1)d}$ we
have \\
$\O_n M^k \O_n=\O_n \overline{M} \O_{n+d}\overline{M} \O_{n+2d}\overline{M} \O_{n+3d} \cdots
\overline{M}\O_n$.\\
Applying Lemma \ref{lem:supercut} repeatedly (from right to left)
we have \\
$\O_n M^k \O_n=\O_n M_d \O_{n+d}\overline{M} \O_{n+2d}\overline{M}
\O_{n+3d} \cdots
\overline{M}\O_n=\O_n \overline{M}^k \O_n$\\
which finishes the proof.
\myqed
\end{pf}


We also need the following technical lemma, translating
certain recursion equations into matrix equations and deriving a
recursion for a matrix product.

\begin{lem}
\label{lem:prodrecur}
Let $F(n,k)$ be defined by
\begin{equation}
\begin{array}{llll}
F(1,k)&=&\delta_{1,k}; \\
F(n,1)&=&\alpha_0 F(n-1,1), &\text{ for } n\geq 2;\\
F(n,k)&=&\alpha_0 F(n-1,k)+\alpha_1 F(n-1,k-1), &\text{ for }
n\geq 2 \text{ and } k\geq 2.
\end{array}
\end{equation}

Let furthermore $G(n,k)$ for all $n\geq 2$ be defined by

\begin{equation}
\begin{array}{llll}
G(n,1)&=&\beta_0 G(n-1,1); &
\\
G(n,2)&=&\beta_0 G(n-1,2) + \beta_1 G(n-1,1);
\\
G(n,k)&=&\beta_0 G(n-1,k) + \beta_1 G(n-1,k-1) \\
&& + \beta_2 G(n-1,k-2), &\text{ for } k\geq 3.
\end{array}
\end{equation}
Then $H=FG$ satisfies the equations
\begin{equation}
\label{def:gdef}
\begin{array}{llll}
H(1,k)&=&G(1,k), &\text{ for all } k\geq 1;\\
H(n,1) &=&(\alpha_0 + \alpha_1 \beta_0)H(n-1,1), &\text{ for }
n\geq 2;
\\
H(n,2) &=&(\alpha_0 + \alpha_1 \beta_0)H(n-1,2)+ \\
&& \alpha_1 \beta_1H(n-1,1), &\text{ for } n\geq 2;
\\
H(n,k) &=&(\alpha_0 + \alpha_1 \beta_0)H(n-1,k)+ \\ && \alpha_1
\beta_1H(n-1,k-1) + \\
&&  \alpha_1 \beta_2H(n-1,k-2), &\text{ for } n\geq 2 \text{ and }
k\geq 3.
\end{array}
\end{equation}
\end{lem}
\begin{pf}
The recursion for $F$ can be rewritten as $\S F= \alpha_0 F +
\alpha_1 F \S$. Defining the matrix $B=\beta_0 \I + \beta_1 \S +
\beta_2 \S^2$ the recursion for $G$ can be written as $\S G = G
B$. Since $F$ has the $(1,0,0,\ldots)$ as its first row, we have
$H(1,k)=G(1,k)$.

Using the matrix representation, we have \\
\begin{equation*}
\begin{split}
\S F G & = (\alpha_0 F + \alpha_1 F \S)G =
 \alpha_0 F G + \alpha_1 F G B \\
& = \alpha_0 F G + \alpha_1 \beta_0 F G +  \alpha_1 \beta_1 F G \S
+ \alpha_1 \beta_2 F G \S^2
\end{split}
\end{equation*}
and this is the matrix form of Equation (\ref{def:gdef}).
\myqed
\end{pf}

We need the following row sum inequality for recursively defined functions.

\begin{lem}\label{lem:rowsum}
Let $F(n,k)$ be defined for $n\geq 1$ and $k\geq 1$ such that only
finitely many of the $F(1,k)$ are nonzero and
$F(n,k)=\sum_{j=0}^{\min(d,k-1)}\alpha_j F(n-1,k-j)$. Then we have
$\sum_{j} F(n,j)\leq
(\sum_{j}|F(1,j)|)(\sum_{l=0}^{d}{|\alpha_l|})^{n-1}$.
\end{lem}
\begin{pf}
The assertion is trivial for $n=1$. \\
For $n>1$ we have $\sum_{j} F(n,j)\leq\sum_{j} |F(n,j)|\leq
\sum_{j} \sum_{l=0}^{d}|F(n-1,j-l)||\alpha_l|$. \myqed
\end{pf}

\begin{rem}\label{rem:lincomb}{\rm Later, we will also use the following
fact: Let the recursively defined matrices $F_i(n,k)$ (defined for
$1\leq i\leq N$) all fulfill the same recursion,
$F_i(n,k)=\sum_{j=0}^{\min(p,k-1)}{\alpha_j F_i(n-1,k-j)}$.\\
 Then
the linear combination $F(n,k)=\sum_{i=1}^{N}\gamma_i F_i(n,k)$
also fulfills the recursion
$F(n,k)=\sum_{j=0}^{\min(p,k-1)}{\alpha_j F(n-1,k-j)}$. We will
use this fact with ``shifted'' functions, defined for $i>0$ by
$F_i(n,k)=F_0(n,k-i)$ for $k\geq i$ and $F_i(n,k)=0$ for $k<i$. }
\end{rem}


\begin{rem}\label{rem:binomsimp}
{\rm We will also make use of the following well known fact:\\
Let $p_d(x)$ be a polynomial of degree $d$. Then for arbitrary
integers $k$ and $n>d$ we have
$\sum_{i=0}^{n}{p_d(k+i)\binom{n}{i}(-1)^i}=0$. \\
This is another way of expressing the fact that a polynomial of
degree $d$ has vanishing finite differences of any order higher
than $d$. \\
In matrix notation, we can rewrite this fact in the following way:
Let $X$ be a matrix with rows generated by polynomials, i.e.,
$X(n,k)=p_{n-1}(k)$, with $p_n$ being polynomials of degree $n$.
Then $X \B'^{-1}=X (\B^{-1})'$ is a (lower) triangular matrix.}
\end{rem}

\section{The proof}
We start with a few more or less technical lemmata, which
finally will result in a proof of Theorems \ref{thm:matrixrep} and
\ref{thm:complexity}. The main technique used is the translation of
recursion equations into matrix equations.

\begin{lem}
Let the infinite matrix $W$ be defined by \\
$W(n,k)=1$ for $k+1\leq n \leq 2k$ and $W(n,k)=0$ everywhere else.
Then the tournament matrix $\U$ satisfies the equation
\begin{equation}
\label{eqn:Tmateqn} \S \U = \U W.
\end{equation}
\end{lem}
\begin{pf}
Equation (\ref{eqn:Tmateqn}) is just a matrix version of Equation
(\ref{eqn:Trecur}). \myqed
\end{pf}

\begin{lem}
\label{lem:Kdef} $\V=\U \B'^{-1}$ is a lower triangular matrix,
and the first columns of $\V$ and $\U$ are equal.
\end{lem}
\begin{pf}
As Cook and Kleber have shown in \cite{klebercookpap}, $T(n,k)$ can be written as
\\$T(n,k)=p_{n-1}(k)$ with $p_n$ being polynomials of degree $n$.
Using Remark \ref{rem:binomsimp} proves the first part of our
lemma. Since the first column of  $\B'^{-1}$ is
$(1,0,0,0,\ldots)'$, the second assertion of the lemma is trivial.
\myqed
\end{pf}

\begin{lem}
\label{lem:Krecur} $\V$ defined in Lemma \ref{lem:Kdef} satisfies
the equation $\S \V= \V D$ \\
with $D=\B'W\B'^{-1}$, and $D$ is 1-supertriangular.
\end{lem}
\begin{pf}
Since we have $\S \U = \U W$ we also have $\S \U \B'^{-1}=\U W
\B'^{-1}$. \\
By Lemma \ref{lem:Kdef}  $\V=\U \B'^{-1}$ is lower triangular.
Therefore, multiplying it with the upper triangular matrix $\B'$
from the
right is a well defined operation and we have
$\V\B'=\U$.\\
Now we want to apply the associative law, which in general is not
applicable for multiplication of infinite matrices. Nevertheless,
the associative law can be applied if all the matrix products
involved are well defined.
Therefore we have\\
$\S\V = \S \U \B'^{-1} = \U W \B'^{-1} = (\U (\B'^{-1} \B')) (W \B'^{-1})=
((\U \B'^{-1}) \B') (W \B'^{-1})=\\
(\U \B'^{-1}) (\B' (W \B'^{-1}))=\V D$.
\myqed
\end{pf}



\begin{lem}For $D$ defined in Lemma \ref{lem:Krecur} we have
$D=C'$ with $C$ defined by Equations \ref{eqn:Cdef}.
\end{lem}
\begin{pf} Using matrix notation we note that $W$ can be written as\\
$W=\J'(\I_2-\I)$ with $\I_2(n,k)=\delta_{n,2k}$. Therefore we have\\
$C=D'=(\B'W\B'^{-1})'=(\B'\J'(\I_2-\I)\B'^{-1})'=
\B^{-1}(\I_2'-\I)\J\B$.\\
Using Remark \ref{rem:binomsimp} we have \\
$C=\B^{-1}(\I_2'-\I)\S\B\T=(\B^{-1}\I_2'\S\B-\B^{-1}\S\B)\T$.\\
Now we use Lemma \ref{lem:prodrecur} to simplify
$\B^{-1}\S\B$
and $\B^{-1}\I_2'\S\B$.\\
Setting $\alpha_0=-1$, $\alpha_1=1$, $\beta_0=1$, $\beta_1=1$,
$G(1,1)=1$ and  $G(1,2)=1$ allows us to compute the recursion
equation for $H_1=\B^{-1}(\S \B)$. The resulting array $H_1$ in
this case has $H_1(1,1)=1$, $H_1(1,2)=1$, $H_1(1,k)=0$ for $k\geq
2$ and fulfills the simple recursion $H_1(n,k)=H_1(n-1,k-1)$.
Therefore, we have $H_1(n,k)=\delta_{n,k}+\delta_{n+1,k}$.\\
To get the recursion equation for $\B^{-1}\I_2'\S\B$ from Lemma
\ref{lem:prodrecur} we note that $\I_2'\S\B$ is the matrix with
rows $3,5,7,...$ from the binomial triangle $\B$. Therefore, to
apply Lemma \ref{lem:prodrecur}, we set $G(1,k)=\binom{2}{k-1}$,
$\beta_0=1$, $\beta_1=2$ and $\beta_2=1$. For $F$ we use
$\alpha_0=-1$ and $\alpha_1=1$. Then $H_2=FG$ for $n\geq 2$ and
$k\geq 3$ fulfills the recursion
\begin{equation}\label{eqn:Htworecur}
H_2(n,k)=2 H_2(n-1,k-1)+H_2(n-1,k-2)
\end{equation}
Additionally, we have $H_2(1,1)=1$, $H_2(1,2)=2$, $H_2(1,3)=1$,
and $H_2(1,k)=0$ for $k\geq 4$.
%
%
%$H_2(2,1)=0$, $H_2(2,2)=2$, and $H_2(n,k)=0$ for $n\geq 3$ and
%$k\leq 2$.
%
It is easy to see that $H_3(n,k)=2^{2n-k-1}\binom{n-1}{k-n}$
satisfies Equation (\ref{eqn:Htworecur}) with $H_2$ replaced by
$H_3$ and therefore (using Remark \ref{rem:lincomb}) any linear
combination $H(n,k)=\sum_{i=0}^{d}{\gamma_i H_3(n,k-n-i)}$
satisfies Equation
(\ref{eqn:Htworecur}) with $H_2$ replaced by $H$.\\
Since we have $H_3(1,k)=\delta_{1,k}$, $H_4$ defined by \\
$H_4(n,k)=H_3(n,k)+2 H_3(n,k-1) + H_3(n,k-2)$ satisfies
$H_4(1,k)=G(1,k)$, the boundary conditions for $H_2$. Since $H_4$
also fulfills the (adapted) recursion (\ref{eqn:Htworecur}),
we have $H_2=H_4$. \\
Rewriting $H_2=H_4$ we have \\$H_2(n,k)=H_3(n,k)+2 H_3(n,k-1) +
H_3(n,k-1)\\\text{\qquad\quad}\;\;\,= 2^{2n-k-1}\binom{n-1}{k-n} +
2 . 2^{2n-k}\binom{n-1}{k-n-1} +
 2^{2n-k+1}\binom{n-1}{k-n-2}\\
 \text{\qquad\quad}\;\;\,=2^{2n-k-1}\bigl(\binom{n-1}{k-n}+
4 \binom{n-1}{k-n-1}+4 \binom{n-1}{k-n-2}\bigr)$
\\
Combining our formulas for $H_2\B^{-1}\I_2'\S\B$ and
$H_1\B^{-1}\S\B$ \\
we have $C=(H_2-H_1)\T$. Using the fact that multiplying any
matrix with $\T$ from the right is the same as ``cutting off'' the
first column of this matrix, and combining $C=(H_2-H_1)\T$ with
the elementwise representations for $H_1$ and $H_2$ this gives
Equations (\ref{eqn:Cdef}) for $C$. \myqed
\end{pf}
Now we are finally ready to prove Theorem
\ref{thm:matrixrep}.

\textbf{Proof of Theorem \ref{thm:matrixrep}} \\
According to Lemma \ref{lem:Kdef} the $T(n)$ are the first column
of $\V$. So $T(n)$ is the upper left element of $\S^{n-1}\V$. Since
$\S \V=\V C'$ we have $S^{n-1}\V=\V (C')^{n-1}$. Since $\V$ is lower
triangular and  $\V(1,1)=1$, the upper left element of $\V
(C')^{n-1}$ is also the upper left element of $(C')^{n-1}$, and, by
transposing, the upper left element of $C^{n-1}$. Applying
Lemma~\ref{lem:superdpower} with $n=1$, $d=1$, and $k=n-1$
finishes the proof of Theorem
\ref{thm:matrixrep}.

\textbf{Proof of Theorem \ref{thm:complexity}} \\
We will discuss computing $T(n+1)$ instead of computing $T(n)$
because then the equations become somewhat simpler. \\
We note that to compute $T(n+1)$ it is not necessary to compute
the complete matrix $C_{n}^{n}$. It is sufficient to compute the
first column of $C_{n}^{n}$. Defining a vector sequence $v_i$ by
$v_0$=$e_1$ (the vector $(1,0,0,0,\ldots)'$ of length $n$) and
$v_{i+1}=C_{n} v_i$ we see that $v_{n}$ is the first column of
$C_{n}^{n}$ and $T(n+1)$ is the first element of $v_{n}$.


The following algorithm computes $v_k$:
\begin{enumerate}
\item
For $1\leq i \leq n$ let $v_0(i)=\delta_{1,i}$
\item\label{item:steptwo}
For $j=1,2,\ldots n$ let $v_j(i)=\sum_{l=1}^{n}C(i,l)v_{j-1}(l)$
\end{enumerate}

Each single execution of step (\ref{item:steptwo}) involves $n^2$
multiplications and $n(n-1)$ additions, and this step is repeated
$n$ times. So the total number of multiplications and additions
for all repeated executions of step (\ref{item:steptwo}) is
$O(n^3)$.\\
To be able to perform these steps we have to calculate the $n^2$
elements of matrix $C$. $C$ essentially contains sums of binomial
coeffients $\binom{N}{k}$ with $N\leq 2n$ multiplied by powers of
2, and therefore can be calculated in time $n^3$.

Using the fact that $C=(H_2-H_1)\T$ we see that
$C(i,j)\leq H_2(i,j+1)$ for all $i$ and $j$.\\
Applying Lemma \ref{lem:rowsum} and the recursion
\ref{eqn:Htworecur} to $H_2$
gives\\
$\sum_{j}{H_2(n,j)}\leq 8\cdot 3^{n-1}$ and therefore trivially
$\max_{i,j\leq n}{H_2(i,j)}\leq 8\cdot 3^{n-1}$. \\
Therefore we also have
$\sum_{j}{C(n,j)}\leq 8\cdot 3^{n-1}$ and
$\max_{i,j\leq n}{C(i,j)}\leq 8\cdot 3^{n-1}$. \\
Therefore, by induction we have
$v_k(i)\leq 8^{k-1} 3^{(n-1)(k-1)}$ and as a consequence
$v_k(i)\leq 8^{n-1} 3^{(n-1)(n-1)}\leq 3^{n^2}$.
So all the multiplications in step (\ref{item:steptwo})
have one factor bounded by $8\cdot 3^{n-1}\leq 3^{n+1}$ and the other factor bounded
by $3^{n^2}$, and for all additions the two summands are bounded by $3^{n^2}$.


To give an estimate for the upper bound for the time needed to
compute $T(n)$, we will use naive bit complexity (as introduced by
Bach and Shallit in \cite{bachshallitbook}), i.e., we assume
that the time needed for addition of large numbers $x$ and $y$ is
bounded by $O(\max(\log(x),\log(y)))$, i.e., the number of digits
of $x$ and $y$, and that the time needed for multiplication of
large numbers $x$ and $y$ is bounded by
$O(\log(x) \log(y))$.  \\
So, to compute the $n^{\text{th}}$ tournament number, we need
$O(n^3)$ operations with naive bit complexity bounded by $O(n^3)$
for each of these operations, and therefore naive bit complexity
for computation is $O(n^6)$. \myqed

\begin{rem}
{\rm The derivation of our complexity bound uses naive bit
complexity, assuming $O(\log(x)\log(y))$ as the bound for the
multiplication of two numbers $x$ and $y$. Faster methods for
multiplying large numbers are known. Using  Karatsuba's
multiplication algorithm (see \cite{karatsubapap}) we get a bound
of $O(n^{4+\log 3})$, or approximately $O(n^{5.6})$ for
complexity, and using Strassen's method (see \cite{strassenpap})
we even could get $O(n^5 \log n \log \log n)$.
%
}
\end{rem}

\section{Practical considerations}
For practical computation purposes it is convenient to use matrix computation
as implemented in modern computer algebra systems. Matrix calculations
are implemented much faster than loops for calculating sums of products.
Here is Mathematica code implementing our algorithm.
\begin{verbatim}
TourCoeff[n_, k_] :=
  2^(2*n - k - 2)*(Binomial[n - 1, k - n + 1] +
          4*Binomial[n - 1, k - n] +
          4*Binomial[n - 1, k - n - 1]) -
          KroneckerDelta[n, k] -
          KroneckerDelta[n, k + 1]

CoeffMat[N_] := Transpose[Table[TourCoeff[i, j],
                      {i, 1, N}, {j, 1, N}]]

Tour[n_] :=
  Module[{C}, C = CoeffMat[n - 1];
    v = Table[KroneckerDelta[i, 1], {i, 1, n - 1}];
    Do[v = v.C, {i, 1, n - 1}]; v[[1]]]
\end{verbatim}
And here is Mathematica code implementing the algorithm of Kleber and Cook.
\begin{verbatim}
TourKleb[1, k_] := TourKleb[1, k] = 1
TourKleb[n_, k_] /; k <= n :=
  TourKleb[n, k] =
    If[k > 1, TourKleb[n, k - 1], 0] - TourKleb[n - 1, k] +
      TourKleb[n - 1, 2*k - 1] + TourKleb[n - 1, 2*k]
TourKleb[n_, k_] /; k > n :=
  TourKleb[n, k] =
     Sum[TourKleb[n, k - j]*Binomial[n, j]*(-1)^(j + 1),
      {j, 1, n}]
TourKleb[n_] := TourKleb[n, 1]
\end{verbatim}
Computing $T(n)$ for selected values of $n$ needed the following
time (in seconds) on a PC with a 1 GHz Pentium processor, Windows 98,
and Mathematica 4.1


\begin{tabular}{l|r|r|r|r}
$n$  & 100 & 150 & 200 & 300 \\
\hline
Kleber-Cook & 24 & 145 & 2344 & \\
Neuwirth & 2 & 16 & 88 & 6107\\
\end{tabular}

We did not compute $T(300)$ with the Kleber-Cook method since that
would have taken far too long.\\
These results might be somewhat surprising since the Kleber-Cook
algorithm and our algorithm have the same asymptotic complexity.
Two facts at least partially explain why our algorithm is much
faster: $T(n,k)$ increases in $k$, and the Kleber-Cook algorithm
computes $T(n,k)$ for $k=1,2,\ldots 2n$. Our algorithm only uses
numbers occurring in $\V$ as defined in Lemma \ref{lem:Kdef} and
the elements of $\V$ are much smaller than the elements of $\U$.
When calculating the product sums in the recursion equations, we
calculate $(n-1)^2$ sums of $n-1$ terms each in our algorithms.
The Kleber-Cook algorithm has $n-1$ steps and in step $i$ computes
$i$ sums for 3 terms and $i$ sums of $i$ terms. So this algorithm
computes fewer sums than our algorithm at the beginning and more
sums at the end. At the end, however, the numbers are larger and
therefore the computations are more time-consuming. Additionally,
rewriting product sums as matrix product speeds up computation
considerably.



\begin{thebibliography}{9}

\bibitem{bachshallitbook}
E. Bach and J. Shallit, {\em Algorithmic Number Theory}.
MIT Press, 1996.

\bibitem{narayanapap}
P. Capelli and T. V. Narayana, On Knock-Out Tournaments. {\em
Canad.\ Math.\ Bull.} {\bf 13} (1970), 105-109.

\bibitem{karatsubapap}
A. Karatsuba and Yu. Ofman, Multiplication of Many-Digital Numbers
by Automatic Computers. {\em Doklady Akad.\ Nauk SSSR} {\bf 145}
(1962) 293-294. \\
Translation in {\em Physics-Doklady} {\bf 7} (1963), 595-596.

\bibitem{kemenypap}
J. G. Kemeny, Matrix representation for combinatorics, {\em J.
Comb.\ Theory Ser.~A} {\bf 36}, (1984), 279-306.


\bibitem{klebercookpap}
M. Cook  and M. Kleber, Tournament sequences and Meeussen
sequences, {\em Electron.\ J. Combin.} {\bf 7} (2000),
Research Paper 44, 16 pp. (electronic).


\bibitem{neuwirthgaltonpap}
E. Neuwirth, Recursively defined combinatorial functions:
extending Galton's board. {\em Discrete Math.} {\bf 239} (2001),
33-51.

\bibitem{sloanenc}
N. J. A. Sloane,  Sloane's On-Line Encyclopedia of Integer
Sequences. \verb+http://www.research.att.com/~njas/sequences/+

\bibitem{strassenpap}
A. Sch\"onhage and V. Strassen, Schnelle Multiplikation gro\ss er
Zahlen. {\em Computing} {\bf 7} (1971), 281-292.


\bibitem{torellirep}
M. Torelli, Increasing Integer Sequences and Goldbach's
Conjecture. {\em Preprint}, (1996).




\end{thebibliography}


\end{document}
