Séminaire Lotharingien de Combinatoire 47 (2002), Article B47h

Computing Tournament Sequence Numbers efficiently with Matrix Techniques

Erich Neuwirth

Department of Statistics and Decision Support Systems University of Vienna

                    erich.neuwirth@univie.ac.at

Abstract

We give a new, “almost explicit” formula for tournament numbers, representing them as upper left elements of the n^{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}).

1 Main results

Tournament sequences are defined as sequences (t_{1}, t_{2}, ....) with t_{1} = 1 and t_{i} < t_{i+1} ≤ 2t_{i}. Defining T_{k}-sequences as sequences with (t_{1}, t_{2}, ....) with t_{1} = k and t_{i} < t_{i+1} ≤ 2t_{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 ≤ i ≤ 2k are the only possible choices for the first element of the extension sequence. Therefore, we have the recursion

T (n, k) = ∑_{j=k+1}^{2k} T (n − 1, j).  (1)

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, … 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 [2]. Further results about T (n) can be found in Sloane’s On-Line Encyclopedia of Integer Sequences [7] (sequence A008934). Tournament numbers have been studied by Torelli (see [9]) in connection with the Goldbach conjecture. Kleber and Cook studied algorithmic aspects of computing T (n) extensively in [5]. 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.

Theorem 1 Let n ≥ 2. Then T (n) is the upper left element of the matrix power C_{n−1}^{n−1} where C_{m} is the m × m-matrix with elements

\begin{aligned}C(i, j) & = & 2^{2i−j−2}(\binom{i−1}{j−i+1} + 4\binom{i−1}{j−i} + 4\binom{i−1}{j−i−1}), \\ & & for i ≠ j and i − 1 ≠ j; \\ C(i + 1, i) & = & 2^{i} − 1; \\ C(i, i) & = & 2^{i−2}(i + 3) − 1; \end{aligned}  (2)

for 1 ≤ i, j ≤ m.

Here are the first few lines and columns of this matrix:

( \begin{matrix}1 & 1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 4 & 4 & 1 & 0 & 0 & 0 & … \\ 0 & 3 & 11 & 13 & 6 & 1 & 0 & … \\ 0 & 0 & 7 & 27 & 38 & 25 & 8 & … \\ 0 & 0 & 0 & 15 & 63 & 104 & 88 & … \\ 0 & 0 & 0 & 0 & 31 & 143 & 272 & … \\ 0 & 0 & 0 & 0 & 0 & 63 & 319 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix})

Theorem 2 Using the representation of Theorem 1, T (n) can be computed in time complexity O(n^{6}).

2 Matrix preliminaries

The key for applying matrix techniques to our problem is the observation that Equation (1) can be interpreted in the following way: Let U be the matrix with elements T (i, j), i ≥ 1, j ≥ 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 ≤ 2j and W (i, j) = 0 everywhere else. Writing the matrices U and W elementwise, we have

( \begin{matrix}T (2, 1) & T (2, 2) & T (2, 3) & T (2, 4) & T (2, 5) & … \\ T (3, 1) & T (3, 2) & T (3, 3) & T (3, 4) & T (3, 5) & … \\ T (4, 1) & T (4, 2) & T (4, 3) & T (4, 4) & T (4, 5) & … \\ T (5, 1) & T (5, 2) & T (5, 3) & T (5, 4) & T (5, 5) & … \\ T (6, 1) & T (6, 2) & T (6, 3) & T (6, 4) & T (6, 5) & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ^{…} \end{matrix} ) = ( \begin{matrix}T (1, 1) & T (1, 2) & T (1, 3) & T (1, 4) & T (1, 5) & … \\ T (2, 1) & T (2, 2) & T (2, 3) & T (2, 4) & T (2, 5) & … \\ T (3, 1) & T (3, 2) & T (3, 3) & T (3, 4) & T (3, 5) & … \\ T (4, 1) & T (4, 2) & T (4, 3) & T (4, 4) & T (4, 5) & … \\ T (5, 1) & T (5, 2) & T (5, 3) & T (5, 4) & T (5, 5) & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ^{…} \end{matrix} )( \begin{matrix}0 & 0 & 0 & 0 & 0 & … \\ 1 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 0 & 0 & 0 & … \\ 0 & 1 & 1 & 0 & 0 & … \\ 0 & 0 & 1 & 0 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ^{…} \end{matrix} )

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 matrix with finite rows, and we call a matrix with columns with only finitely many nonzero elements a matrix with finite columns.

In our case, matrix W has finite rows and finite columns, and therefore rewriting recursion (1) as matrix equation is possible. Furthermore, any infinite matrix can be multiplied with W from the left and from the right.

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 [4] and extensively used by Neuwirth in [6].

For our proof, we will need some “helper matrices”. We will use infinite matrices. All our matrices start with row 1 and column 1. δ_{i,j} is the standard Kronecker symbol, defined by δ_{i,i} = 1 and δ_{i,j} = 0 fori ≠ j. I defined by I(n, k) = δ_{n,k} is the identity matrix. S defined by S(n, k) = δ_{n+1,k} is a matrix with 1s just above the main diagonal and 0s everywhere else.

T defined by T (n, k) = δ_{n,k+1} is a matrix with 1s just below the main diagonal and 0s everywhere else. O_{n} defined by O_{n}(m, k) = δ_{m,k} for m ≤ 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 ≥ k and J (n, k) = 0 for n < k is a lower triangular matrix with 1s 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:

ST = I  (3)
(I − T )^{−1} = J  (4)

For a (lower) triangular matrix D we have

O_{n}D = O_{n}DO_{n}  (5)

Furthermore we also have

O_{n}O_{m} = O_{min(m,n)}  (6)
O_{n}S^{k} = S^{k}O_{n+k}  (7)

and

J B = (I − T )^{−1}B = SBT  (8)

The last equation is just “the matrix way” of rewriting ∑_{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}DO_{n} is the “left upper n×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:

Lemma 3 Let D be triangular. Then O_{n}D^{k}O_{n} = (O_{n}DO_{n})^{k}.

PROOF. This is an immediate consequence of Equation (5). □

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.

Definition 4 A matrix M is called d-supertriangular if M(n, k) = 0 for k > n + d.

Lemma 5 M is d-supertriangular iff there exists a triangular matrix D with M = S^{d}D.

PROOF. Trivial. □

Lemma 6 For a d-supertriangular matrix M we have O_{n}M = O_{n}MO_{n+d}.

PROOF. According to Lemma 5 we have M = S^{d}D with a triangular matrix D. Therefore, using Equation (7) we have O_{n}M = O_{n}S^{d}D = S^{d}O_{n+d}D. Using Equation (5) we have S^{d}O_{n+d}D = S^{d}O_{n+d}DO_{n+d}. Using Equation (7) again we have S^{d}O_{n+d}DO_{n+d} = O_{n}S^{d}DO_{n+d} = O_{n}MO_{n+d}.

□

Lemma 7 For a d-supertriangular matrix M we have O_{n}M^{k}O_{n} = O_{n}(O_{n+(k−1)d}MO_{n+(k−1)d})^{k}O_{n}.

PROOF. Using Lemma 6 we have O_{n}M^{k}O_{n} = O_{n}MM^{k−1}O_{n} = O_{n}MO_{n+d}M^{k−1}O_{n}. Applying Lemma 6 repeatedly from left to right following this pattern we have O_{n}M^{k}O_{n} = O_{n}MO_{n+d}MO_{n+2d}MO_{n+3d} ⋯ O_{n+(k−1)d}MO_{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 ≤ 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}MO_{n+(k−1)d}O_{n+d}

· O_{n+(k−1)d}MO_{n+(k−1)d}O_{n+2d}

· O_{n+(k−1)d}MO_{n+(k−1)d}O_{n+3d} ⋯
· O_{n+(k−1)d}MO_{n+kd}O_{n+(k−1)d}O_{n}

Since \overline{M} = O_{n+(k−1)d}MO_{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} ⋯ \overline{M}O_{n}. Applying Lemma 6 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} ⋯ \overline{M}O_{n} = O_{n}\overline{M}^{k}O_{n} which finishes the proof. □

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

Lemma 8 Let F (n, k) be defined by

F (1, k) = δ_{1,k};
F (n, 1) = α_{0}F (n − 1, 1),  for n ≥ 2;
F (n, k) = α_{0}F (n − 1, k) + α_{1}F (n − 1, k − 1), for n ≥ 2 and k ≥ 2.

(9)

Let furthermore G(n, k) for all n ≥ 2 be defined by

\begin{aligned}G(n, 1) & = & β_{0}G(n − 1, 1); \\ G(n, 2) & = & β_{0}G(n − 1, 2) + β_{1}G(n − 1, 1); \\ G(n, k) & = & β_{0}G(n − 1, k) + β_{1}G(n − 1, k − 1) \\ & & +β_{2}G(n − 1, k − 2), & for k ≥ 3. \end{aligned}  (10)

Then H = F G satisfies the equations

H(1, k) = G(1, k),  for all k ≥ 1;
H(n, 1) = (α_{0} + α_{1}β_{0})H(n − 1, 1), for n ≥ 2;
H(n, 2) = (α_{0} + α_{1}β_{0})H(n − 1, 2)+
α_{1}β_{1}H(n − 1, 1),  for n ≥ 2;
H(n, k) = (α_{0} + α_{1}β_{0})H(n − 1, k)+
α_{1}β_{1}H(n − 1, k − 1)+
α_{1}β_{2}H(n − 1, k − 2),  for n ≥ 2 and k ≥ 3.

(11)

PROOF. The recursion for F can be rewritten as SF = α_{0}F + α_{1}F S. Defining the matrix B = β_{0}I + β_{1}S + β_{2}S^{2} the recursion for G can be written as SG = GB. Since F has the (1, 0, 0, …) as its first row, we have H(1, k) = G(1, k).

Using the matrix representation, we have

\begin{aligned}SF G & = (α_{0}F + α_{1}F S)G = α_{0}F G + α_{1}F GB \\ & = α_{0}F G + α_{1}β_{0}F G + α_{1}β_{1}F GS + α_{1}β_{2}F GS^{2} \end{aligned}

and this is the matrix form of Equation (11). □

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

Lemma 9 Let F (n, k) be defined for n ≥ 1 and k ≥ 1 such that only finitely many of the F (1, k) are nonzero and F (n, k) = ∑_{j=0}^{min(d,k−1)} α_{j}F (n − 1, k − j). Then we have ∑_{j} F (n, j) ≤ (∑_{j} |F (1, j)|)(∑_{l=0}^{d} |α_{l}|)^{n−1}.

PROOF. The assertion is trivial for n = 1. For n > 1 we have ∑_{j} F (n, j) ≤ ∑_{j} |F (n, j)| ≤ ∑_{j} ∑_{l=0}^{d} |F (n − 1, j − l)||α_{l}|.

□

Remark 10 Later, we will also use the following fact: Let the recursively defined matrices F_{i}(n, k) (defined for 1 ≤ i ≤ N) all fulfill the same recursion, F_{i}(n, k) = ∑_{j=0}^{min(p,k−1)} α_{j}F_{i}(n − 1, k − j). Then the linear combination F (n, k) = ∑_{i=1}^{N} γ_{i}F_{i}(n, k) also fulfills the recursion F (n, k) = ∑_{j=0}^{min(p,k−1)} α_{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 ≥ i and F_{i}(n, k) = 0 for k < i.

Remark 11 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 ∑_{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 XB^{′−1} = X(B^{−1})′ is a (lower) triangular matrix.

3 The proof

We start with a few more or less technical lemmata, which finally will result in a proof of Theorems 1 and 2. The main technique used is the translation of recursion equations into matrix equations.

Lemma 12 Let the infinite matrix W be defined by W (n, k) = 1 for k + 1 ≤ n ≤ 2k and W (n, k) = 0 everywhere else. Then the tournament matrix U satisfies the equation

SU = UW.  (12)

PROOF. Equation (12) is just a matrix version of Equation (1). □

Lemma 13 V = UB^{′−1} is a lower triangular matrix, and the first columns of V and U are equal.

PROOF. As Cook and Kleber have shown in [5], T (n, k) can be written as T (n, k) = p_{n−1}(k) with p_{n} being polynomials of degree n. Using Remark 11 proves the first part of our lemma. Since the first column of B^{′−1} is (1, 0, 0, 0, …)′, the second assertion of the lemma is trivial. □

Lemma 14 V defined in Lemma 13 satisfies the equation SV = VD with D = B′W B^{′−1}, and D is 1-supertriangular.

PROOF. Since we have SU = UW we also have SUB^{′−1} = UW B^{′−1}. By Lemma 13 V = UB^{′−1} is lower triangular. Therefore, multiplying it with the upper triangular matrix B′ from the right is a well defined operation and we have VB′ = 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 SV = SUB^{′−1} = UW B^{′−1} = (U(B^{′−1}B′))(W B^{′−1}) = ((UB^{′−1})B′)(W B^{′−1}) = (UB^{′−1})(B′(W B^{′−1})) = VD. □

Lemma 15 For D defined in Lemma 14 we have D = C′ with C defined by Equations 2.

PROOF. Using matrix notation we note that W can be written as W = J′(I_{2} − I) with I_{2}(n, k) = δ_{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 11 we have C = B^{−1}(I′_{2} − I)SBT = (B^{−1}I′_{2}SB − B^{−1}SB)T . Now we use Lemma 8 to simplify B^{−1}SB and B^{−1}I′_{2}SB. Setting α_{0} = −1, α_{1} = 1, β_{0} = 1, β_{1} = 1, G(1, 1) = 1 and G(1, 2) = 1 allows us to compute the recursion equation for H_{1} = B^{−1}(SB). 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 ≥ 2 and fulfills the simple recursion H_{1}(n, k) = H_{1}(n − 1, k − 1). Therefore, we have H_{1}(n, k) = δ_{n,k} + δ_{n+1,k}. To get the recursion equation for B^{−1}I′_{2}SB from Lemma 8 we note that I′_{2}SB is the matrix with rows 3, 5, 7, ... from the binomial triangle B. Therefore, to apply Lemma 8, we set G(1, k) = \binom{2}{k−1}, β_{0} = 1, β_{1} = 2 and β_{2} = 1. For F we use α_{0} = −1 and α_{1} = 1. Then H_{2} = F G for n ≥ 2 and k ≥ 3 fulfills the recursion

H_{2}(n, k) = 2H_{2}(n − 1, k − 1) + H_{2}(n − 1, k − 2)  (13)

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 ≥ 4. It is easy to see that H_{3}(n, k) = 2^{2n−k−1}\binom{n−1}{k−n} satisfies Equation (13) with H_{2} replaced by H_{3} and therefore (using Remark 10) any linear combination H(n, k) = ∑_{i=0}^{d} γ_{i}H_{3}(n, k − n − i) satisfies Equation (13) with H_{2} replaced by H. Since we have H_{3}(1, k) = δ_{1,k}, H_{4} defined by H_{4}(n, k) = H_{3}(n, k) + 2H_{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 (13), we have H_{2} = H_{4}. Rewriting H_{2} = H_{4} we have H_{2}(n, k) = H_{3}(n, k) + 2H_{3}(n, k − 1) + H_{3}(n, k − 1)

= 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}

= 2^{2n−k−1}(\binom{n−1}{k−n} + 4\binom{n−1}{k−n−1} + 4\binom{n−1}{k−n−2})

Combining our formulas for H_{2}B^{−1}I′_{2}SB and H_{1}B^{−1}SB 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 (2) for C. □

Now we are finally ready to prove Theorem 1.

Proof of Theorem 1 According to Lemma 13 the T (n) are the first column of V. So T (n) is the upper left element of S^{n−1}V. Since SV = VC′ 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 7 with n = 1, d = 1, and k = n − 1 finishes the proof of Theorem 1.

Proof of Theorem 2 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, …)′ 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}:

(1) For 1 ≤ i ≤ n let v_{0}(i) = δ_{1,i}

(2) For j = 1, 2, … n let v_{j}(i) = ∑_{l=1}^{n} C(i, l)v_{j−1}(l)

Each single execution of step (2) 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 (2) 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 ≤ 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) ≤ H_{2}(i, j + 1) for all i and j. Applying Lemma 9 and the recursion 13 to H_{2} gives ∑_{j} H_{2}(n, j) ≤ 8 · 3^{n−1} and therefore trivially max_{i,j≤n} H_{2}(i, j) ≤ 8 · 3^{n−1}. Therefore we also have ∑_{j} C(n, j) ≤ 8 · 3^{n−1} and max_{i,j≤n} C(i, j) ≤ 8 · 3^{n−1}. Therefore, by induction we have v_{k}(i) ≤ 8^{k−1}3^{(n−1)(k−1)} and as a consequence v_{k}(i) ≤ 8^{n−1}3^{(n−1)(n−1)} ≤ 3^{n^{2}}. So all the multiplications in step (2) have one factor bounded by 8 · 3^{n−1} ≤ 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 [1]), 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^{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}). □

Remark 16 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 [3]) we get a bound of O(n^{4+log 3}), or approximately O(n^{5.6}) for complexity, and using Strassen’s method (see [8]) we even could get O(n^{5} log n log log n).

4 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.

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]]]

And here is Mathematica code implementing the algorithm of Kleber and Cook.

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]

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

n  100 150 200 300
Kleber-Cook 24 145 2344
Neuwirth  2 16 88 6107

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, … 2n. Our algorithm only uses numbers occurring in V as defined in Lemma 13 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.

References

[1] E. Bach and J. Shallit, Algorithmic Number Theory. MIT Press, 1996.

[2] P. Capelli and T. V. Narayana, On Knock-Out Tournaments. Canad. Math. Bull. 13 (1970), 105-109.

[3] A. Karatsuba and Yu. Ofman, Multiplication of Many-Digital Numbers by Automatic Computers. Doklady Akad. Nauk SSSR 145 (1962) 293-294. Translation in Physics-Doklady 7 (1963), 595-596.

[4] J. G. Kemeny, Matrix representation for combinatorics, J. Comb. Theory Ser. A 36, (1984), 279-306.

[5] M. Cook and M. Kleber, Tournament sequences and Meeussen sequences, Electron. J. Combin. 7 (2000), Research Paper 44, 16 pp. (electronic).

[6] E. Neuwirth, Recursively defined combinatorial functions: extending Galton’s board. Discrete Math. 239 (2001), 33-51.

[7] N. J. A. Sloane, Sloane’s On-Line Encyclopedia of Integer Sequences.

   http://www.research.att.com/~njas/sequences/

[8] A. Schönhage and V. Strassen, Schnelle Multiplikation großer Zahlen. Computing 7 (1971), 281-292.

[9] M. Torelli, Increasing Integer Sequences and Goldbach’s Conjecture. Preprint, (1996).