\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
Counting Tournament Brackets
}
\vskip 1cm
\large
John P. D'Angelo \\
Department of Mathematics \\
University of Illinois \\
1409 W. Green St. \\
Urbana, IL 61801 \\
USA \\
\href{mailto:jpda@illinois.edu}{\tt jpda@illinois.edu} \\
\end{center}
\vskip .2 in
\begin{abstract} Motivated by a question involving tournament brackets, we study the number $W(N)$ of $N$-tuples satisfying a system of natural inequalities.
Our analysis yields a doubly-indexed recurrence relation evoking Pascal's formula and an interesting sequence of polynomials.
We provide upper and lower bounds for $W(N)$ (which grows faster than exponentially) and methods for computing it.
\end{abstract}
\section{Introduction}
The combinatorial problems studied in this paper arise from a recreational context involving brackets in a tournament with $2^N$ teams.
We solve several natural problems in this setting and also discover an interesting sequence of polynomials. One basic question is to count the number $W(N)$ of what we call {\it valid brackets\/}
in such a tournament; the first few values are
$2,5,19,123,1457, 32924$. This is a new sequence with number
\seqnum{A355519} in the {\it On-Line Encyclopedia of Integer Sequences}
\cite{OEIS}, submitted by the author.
Since the sequence is so natural, we determine its basic properties. The analysis leads to additional worthwhile information.
To motivate the definition of $W(N)$ we consider a tournament with $2^N$ teams. In the first round, each team plays once, and the losers are eliminated. The winners play in the second round,
and this process continues until the {\it final winner\/} is determined. Each team except the final winner loses exactly once, and hence $2^N -1$ games are played.
Each March such tournaments are played in college basketball with $N=6$, although the men's tournament has four extra so-called play-in games. Many fans predict the entire tournament before any games are played;
the term {\it bracket\/} is often used to describe the picks (predictions) of a fan. We call such a fan a {\it contestant}.
The odds of a perfect bracket are minuscule. Hence various methods have been devised to evaluate the brackets submitted by contestants. Some of these methods
will be discussed in \cite{DN}. The purpose of the present paper is not to evaluate brackets, but rather to discuss some combinatorial issues that arise when one studies how the number of brackets
depends on the number of rounds $N$.
Our starting point is to identify a bracket with an $N$-tuple. After the tournament has finished, for each contestant we count the number $x_j$ of correct picks in round $j$.
Such $N$-tuples are completely determined by the following system of inequalities:
\begin{definition} A {\it valid bracket\/} or a {\it valid} $N$-{\it tuple\/} is an $N$-tuple
$${\bf x} = (x_1,x_2,\ldots,x_N)$$ of non-negative integers satisfying the inequalities
\begin{equation}\label{x1} x_1 \le 2^{N-1} \end{equation}
\begin{equation} \label{x2} x_{j+1} \le \min(x_j, 2^{N-j-1}) \end{equation}
for $1 \le j \le N-1$.
The number of such $N$-tuples is donated by $W(N)$.
\end{definition}
To introduce the ideas in this paper, we first list all the valid $N$-tuples for $N\le 3$ and then give three additional values of $W(N)$.
These numbers are computed in Section~\ref{two}. We naturally ask several questions. Is there a useful method for describing all valid $N$-tuples? Is it possible to count them for a given $N$?
What is the resulting mathematical structure?
\begin{itemize}
\item For $N=1$, the valid $N$-tuples are $1$ and $0$.
\item For $N=2$, the valid $N$-tuples are $(2,1)$, $(2,0)$, $(1,1)$, $(1,0)$, and $(0,0)$.
\item For $N=3$, there are $19$ valid $N$-tuples, as follows:
\begin{flalign*} &(4,2,1), (4,2,0), (4,1,1), (4,1,0), (4,0,0) & \\
& (3,2,1), (3,2,0), (3,1,1), (3,1,0), (3,0,0) &\\
& (2,2,1), (2,2,0), (2,1,1), (2,1,0), (2,0,0) &\\
& (1,1,1), (1,1,0), (1,0,0) &\\
& (0,0,0).
\end{flalign*}
\item $W(4)=123$. $W(5)=1457$. $W(6)=32924$.\end{itemize}
We will organize the situation using matrices. To do so, let $A(N,k)$ denote the number of valid $N$-tuples with $x_1=k$. By inequality (2), $k$ is also the maximum of the $x_j$.
For fixed $N$, the numbers $A(N,k)$ form a row of a matrix; for fixed $k$ these numbers form a column of this matrix.
The matrix efficiently lists all the relevant information. Given that there are $2^N$ teams, we look at the $N$-th row of the matrix. The zero-th column is the number of brackets (namely $1$)
that get every pick wrong! The next column is the number of brackets that get exactly one correct in the first round, the next column is the number that get exactly 2 right in the first round, and so on.
The numbers increase (as far as they can) because the more picks one gets right in the first round, the more possibilities there are for subsequent rounds.
Finally, in the $N$-th row, all entries are $0$ for $k > 2^{N-1}$. The number of correct picks cannot exceed the number of games!
We show that entries in this matrix satisfy a beautiful doubly-indexed recurrence relation evocative of Pascal's formula for binomial coefficients. Things are more complicated however! For fixed $k$ and $n\ge k-1$, the number $A(n,k)$ is a polynomial of degree $k$ in $n$. Since $W(N)$ is the sum of the entries in the $N$-th row, and $k$ varies from $0$ up to $2^{N-1}$, the sequence $W(N)$ grows faster than exponentially in $N$. We will therefore provide upper and lower bounds as well as its first $16$ values. See Section~\ref{three}.
The following information determines the matrix ${\mathcal A} = A(N,k)$ for $1\le N$ and $0 \le k$. The far left column (corresponding to $k=0$) of ${\mathcal A}$ consists of all ones. By inequality (\ref{x2}), for each $N$, $x_1=0$ implies $x_j=0$ for $1\le j \le N$.
The first entry in the next column is also $1$. As noted above, in a one round tournament, $x_1 =1$ is the only possibility with $k=1$. By definition, in the $N$-th row, all entries are $0$ for
$k > 2^{N-1}$. The remaining entries are determined by the recurrence in Proposition \ref{recurrence}. To repeat, $W(N)$ is the sum of the entries in the $N$-th row.
The crucial point follows from Proposition \ref{recurrence}. Each row determines the next according to the following rule.
Each entry is the sum of the entry above it and the entry to its left, as long as the index $k$ is at most $2^{N-1}$. This recurrence has the following surprising consequence.
For $n\ge k-1$, the number $A(n,k)$ is a polynomial of degree $k$ in the variable $n$. See Proposition \ref{polynomial1} and Theorem \ref{poly-theorem}.
Section~\ref{two} provides details of this matrix analysis.
Section~\ref{three} provides bounds for $W(N)$ and related information.
Section~\ref{four} summarizes the discussion and returns to the original motivation.
\section{Matrix interpretation}
\label{two}
For each positive integer $N$ and each non-negative integer $k$ we define $A(N,k)$ to be the number of valid $N$-tuples $(x_1,\ldots,x_N)$ such that $x_1=k$ and, for each
$j$ we have $x_{j+1} \le \min(x_j, 2^{N-j-1})$. Note that $A(N,k)=0$ for $k > 2^{N-1}$. We let ${\mathcal A}$ denote the infinite matrix whose $N$-th row consists of the numbers
$A(N,0), A(N,1), \ldots, A(N,2^{N-1}), 0, 0, \ldots$.
\begin{proposition} \label{prop1} The following statements hold for the matrix ${\mathcal A}$:
\begin{itemize}
\item If $N\ge 1$, then $A(N,0) =1$. (The far left (zero-th) column is all ones.)
\item If $k > 2^{N-1}$, then $A(N,k) = 0$. (Fill out each row with zeroes.)
\item $A(N,1)=N$ for all $N$.
\item $\left( A(1,0), A(1,1), \ldots \right) = (1,1, 0, \ldots)$ (The first row)
\item $\left( A(2,0), A(2,1), A(2,2), A(2,3), \ldots \right) = (1,2,2,0, \ldots)$ (The second row)
\item $\left( A(3,0), A(3,1), A(3,2), \ldots, A(3,5), \ldots \right) = \left(1,3,5,5,5,0, \ldots \right)$
\end{itemize}
\end{proposition}
\begin{proof}
The first item holds because, if $x_1=0$, then inequality (2) forces $x_j=0$ for all $j$. The second item holds by definition, because $k$ cannot exceed $2^{N-1}$.
The third item holds because putting $x_1=1$ allows $N$ possible choices for the rest of the $x_j$. (They can all be $1$, or all but the last can be $1$, and so on until all are $0$.)
Next consider the first row. By the first item, $A(1,0)=1$. By the third item, $A(1,1)=1$. The remaining entries equal $0$ by the second item. Thus the item corresponding to the first row holds.
To find the second and third rows we anticipate the recurrence relation in Proposition \ref{recurrence}. We have already computed $A(2,0)$ and $A(2,1)$.
To find $A(2,2)$, we note that we are finding all pairs of the form $(2,B)$ where $B$ is either $1$ or $0$. Since $2^{2-1}=2$, we have $A(2,k) = 0$ for $k\ge 3$.
Thus the second row is as described. Consider the third row. Again we already have computed $A(3,0)$ and $A(3,1)$. The possible brackets counted by $A(3,2)$ are those triples
of the form $(2,B,C)$ where $0 \le B \le 2$ and $0 \le C \le \min(1,B)$. There are five such triples. Note that the same holds for $(3,B,C)$ and $(4,B,C)$. Since $5 > 2^{3-1}$, we have $A(3,k) =0$ for $k \ge 5$.
Thus the third row is as described.
\end{proof}
\begin{proposition} \label{recurrence} If $1 \le k \le 2^{N-1}$, then
$$ A(N+1,k) = A(N+1,k-1) + A(N,k).$$ \end{proposition}
\begin{proof} The statement holds when $k=1$, because
$$ A(N+1,1) = N+1 = A(N,1) + A(N+1,0). $$
One can then prove the formula inductively. Instead we proceed directly.
Fix $K$. There are two types of terms contributing to $A(N+1,K)$.
There are $(N+1)$-tuples of the form $(K,K, x_2, \ldots, x_N)$ and those of the form $(K,L, x_2, \ldots, x_N)$ where $L < K$.
The number of terms of the first type is $A(N,K)$. Consider the second type of $(N+1)$-tuple. Since $K$ is fixed and $L\le K-1$, the number of such tuples is the same as the number of valid tuples of the form
$(K-1,L, x_2, \ldots, x_N)$. Hence there are $A(N+1,K-1)$ of this type.
Therefore the recurrence
$$ A(N+1,K) = A(N,K) + A(N+1,K-1) $$
holds, as desired. \end{proof}
\begin{example} We illustrate the subtle step in the proof by considering the special case $A(4,4)$. The recurrence states that $A(4,4) = A(3,4) +A(4,3)$.
The first type of $4$-tuple is $(4,4,C,D)$. There are $5$ of these, where the choices of $(C,D) $ are
$$ (2,1), \ (2,0), \ (1,1), \ (1,0), \ (0,0). $$
The second type is anything of the forms $(4,3,C,D)$, $(4,2,C,D)$, $(4,1,C,D)$, or $(4,0,C,D)$. In each of these cases, the number of possibilities
is the same if we replace the $4$ in the first slot with a $3$. Thus we are counting valid brackets of the form $(3,B,C,D)$. The $14$ possibilities for $(B,C,D)$ are
$$ (3,2,1), \ (3,2,0), \ (3,1,1), \ (3,1,0) \ (3,0,0) \ $$
$$ (2,2,1), \ (2,2,0), \ (2,1,1), \ (2,1,0) \ (2,0,0) \ $$
$$ (1,1,1), \ (1,1,0), \ (1,0,0), \ (0,0,0). $$
\end{example}
\begin{corollary}\label{cor1} For $N \ge 1$, we have $A(N+1,k) = \sum_{j=0}^k A(N,j)$. \end{corollary}
\begin{proof} First, using the recurrence, replace the $A(N+1,k-1)$ term on the right-hand side of the recurrence in the proposition. This yields
$$ A(N+1,k) = A(N+1,k-1) + A(N,k) = A(N+1,k-2) + A(N,k-1) + A(N,k) $$
and continuing the same procedure yields
$$ A(N+1,k) = A(N+1,k-1) + A(N,k) = \cdots = A(N+1, 0) + \sum_{j=1}^ {k-1} A(N,j).$$
Since $1= A(N+1,0) = A(N,0)$, the result follows.
\end{proof}
\begin{remark} Assume $k \le 2^{N}$. Proposition \ref{recurrence} tells us that $A(N+1,k)$ is the sum of two entries, one directly above and the other directly to its left.
Corollary \ref{cor1} tells us that $A(N+1,k)$ is the sum of the entries in the row directly above that are to the left, including the entry directly above.
\end{remark}
The following result is obvious but we want to state it explicitly.
\begin{proposition}$W(N)$ is the sum of the entries in the $N$-th row of ${\mathcal A}$. Thus
$$W(N) = \sum_{k=0}^{2^{N-1}} A(N,k). $$ \end{proposition}
For convenience we write down the next few rows of ${\mathcal A}$. Using the recurrence from Proposition \ref{recurrence}, here are the first four rows of the matrix:
$$ \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr 1&2 & 2& 0 &0 & 0 & 0 & 0 & 0 \cr 1 & 3 & 5 & 5 & 5 & 0 & 0 & 0 & 0 \cr 1 & 4 & 9 & 14 & 19 & 19 & 19 & 19 & 19 \end{pmatrix} $$
Since $2^{4-1} +1 = 9$, there must be nine columns. Since $2^{3-1}+1 = 5$, there must also be five terms equal to $19$.
We consider the next two rows. The fifth row is
$$ 1, 5, 14, 28, 47, 66, 85, 104, 123, 123, 123, 123, 123, 123, 123, 123, 123, 0, \ldots$$
There are nine copies of $123$, because nine numbers $m$ satisfy $8 \le m \le 16$.
When $N=6$ the previous rows are the same but with many zeroes included in the far right columns.
The final row (which takes several lines to list!) is
$$ 1, 6, 20, 48, 95, 161, 246, 350, 473, 596, 719, 842, 965, 1088, 1211, 1334, $$
$$ 1457, 1457, 1457, 1457, 1457, 1457, 1457, 1457, 1457, 1457, 1457, 1457, $$
$$ 1457, 1457, 1457, 1457, 1457, 0, 0, \ldots$$
where there are $17$ copies of $1457$. Seventeen is the number of integers $m$ satisfying $16 \le m \le 32$, and $1457$ is the value of $W(5)$.
Summing this row shows that $W(6)=32924$.
To illustrate our results, consider the entry $596$ in row $6$. It is the sum of $123$ and $473$, namely the sum of the entries directly above and to the left.
It is also the sum $1 +5 + 14 + 28 + 47 + 66 + 85 +104 +123+123$, namely the appropriate sum from the row above.
\begin{proposition} \label{polynomial1} The numbers $A(N,k)$ satisfy the following:
\begin{itemize}
\item $A(N,0) = 1$ for all $N$.
\item $A(N,1)=N$ for all $N$.
\item $A(N,2) = \frac{N^2 + N -2}{2}$ for $N\ge 1$.
\item $A(N,3) = \frac{N^3 + 3N^2 - 4N - 12}{6}$ for $N\ge 2$.
\item $A(N,4) = \frac{N^4 + 6N^3 - N^2 - 54 N + 48}{24}$ for $N\ge 3$.
\item $A(n,k)$ is a polynomial of degree $k$ in the variable $n$ for $n\ge k-1$.
\end{itemize}
\end{proposition}
\begin{proof}
The first two items are obvious and have been noted previously. We next prove the last item by induction on $k$. Recall that
\begin{equation} \label{poly-sum} A(N+1, k) = A(N,k) + \sum_{j=0}^{k-1} A(N, j). \end{equation}
Formula (\ref{poly-sum}) holds for $k=1$, as it says that $N+1= N+1$. Fix $k$. The terms in the sum have smaller values in the second slot and by induction on $k$ can be considered known.
Formula (\ref{poly-sum}) defines a first order linear recurrence for $A(N,k)$. The homogeneous equation is simply $A(N+1,k)= A(N,k)$. The solutions of this equation are simply the constants.
By the induction hypothesis, the inhomogeneous terms of the recurrence form a polynomial of degree $k-1$. Hence the general solution is a polynomial of degree at most $k$. Reference \cite{W}, for example,
discusses such recurrences. We determine this polynomial completely
by specifying its first $k+1$ values, and it must be degree $k$ because the matrix of coefficients of the linear system is invertible. We illustrate in the next example.
\end{proof}
\begin{corollary} For each $k$, there is a polynomial $p_k(N)$ of degree $k$ such that $A(N,k) = p_k(N)$ whenever $N\ge k-1$. As a consequence, for $N\ge k-1$, the entries
in the $k$-th column are simply the values of this polynomial at $N$.
\end{corollary}
The method of determining the matrix and then computing $W(n)$ by summing rows is straightforward albeit tedious. Perhaps the polynomials themselves are more interesting,
and hence we list the first six polynomials that arise. These polynomials are obtained by using the Lagrange interpolation formula. We know these polynomials are of degree $k$, and hence they are determined by $k+1$ of their values.
\begin{theorem} \label{poly-theorem} The polynomials $p_k$ described above are given by
\begin{align*}
& p_0(x) = 1 & \\
& p_1(x) = x & \\
& p_2(x) = \frac{x^2}{2} + \frac{x}{2} -1 & \\
& p_3(x) = \frac{x^3}{6} + \frac{x^2 }{ 2} - \frac{2x} {3} - 2 & \\
& p_4(x) = \frac{x^4}{24} + \frac{x^3} {4}- \frac{x^2}{24} - \frac{9x}{4} + 2 & \\
& p_5(x) = \frac {x^5} {120} + \frac{x^4}{12} + \frac{x^3} { 8} - \frac{13x^2}{12} + \frac{13x} {15} - 5 & \\
& p_6(x) = \frac{x^6 } {720} + \frac{x^5} {48} + \frac{11 x^4} {144} - \frac{13x^3}{48} - \frac{7x^2} {90} -\frac{19x}{4} + 10.
\end{align*}
\end{theorem}
Since these polynomials map the integers to the integers, each can be written as an integer combination of the polynomials $1, x, \frac{x(x-1)} {2}, \frac{x(x-1)(x-2)}{3!}, \ldots$.
As usual, we write these polynomials using binomial coefficient notation.
It is natural to express the $p_k$ in this fashion. We have the following simpler looking formulas, although no clear pattern appears:
\begin{align*}
& p_0(x) = 1 & \\
& p_1(x) = {x \choose 1} & \\
& p_2(x) = -1 + {x \choose 1} + {x \choose 2} & \\
& p_3(x) = -2 + 2 {x \choose 2} + {x \choose 3} & \\
& p_4(x) = 2 - 2 {x \choose 1} + 2 {x \choose 2} + 3{x \choose 3} + {x \choose 4} & \\
& p_5(x) = -5 + 5{x \choose 3} + 4 {x \choose 4} + {x \choose 5} & \\
& p_6(x) = 10 -5 {x \choose 1} + 5 {x \choose 3} + 9 {x \choose 4} + 5 {x \choose 5} + {x \choose 6}.
\end{align*}
\section{Bounds}
\label{three}
First we provide a list of values of $W(N)$. Then we give upper and lower bounds.
Dan Putnam \cite{P} coded the values of $W(N)$ for $N\le 16$ using the method of summing the rows of ${\mathcal A}$. The first 16 values appear in
Figure~\ref{fig1}.
\begin{figure}[htb]
\begin{align*}
W(1) &= 2 \\
W(2) &= 5 \\
W(3) &= 19 \\
W(4) &= 123 \\
W(5)&= 1457 \\
W(6)&= 32924 \\
W(7) &= 1452015 \\
W(8) &= 126487061 \\
W(9) &= 21898598245 \\
W(10) &= 7558601003617 \\
W(11) &= 5209629536999054 \\
W(12) &= 7175576970776253311 \\
W(13) &= 19758953061561609438197 \\
W(14) &= 108796404018098314291373545 \\
W(15) &= 1197986411771818785507163602609 \\
W(16) &= 26381385902615283298043180284145933.
\end{align*}
\caption{The values of $W(N)$ for $1\leq N \leq 16$.}
\label{fig1}
\end{figure}
It is natural to seek upper and lower bounds for $W(N)$ and to describe the growth rate of this sequence. We obtain a useful lower bound simply by dropping the terms $A(n,k)$ that are hard to compute
and we obtain an upper bound by setting all these terms equal to the maximum. We obtain the following inequalities.
\begin{proposition} For each $n\ge 2$, we have
\begin{equation} \label{growth1} (2^{n-2} + 1) W(n-1) < W(n) < ( 2^{n-1} + 1) W(n-1). \end{equation}
As a consequence,
\begin{equation} \label{growth2} (2^{n-2} + 1) < \frac{W(n)}{W(n-1)} < ( 2^{n-1} + 1). \end{equation}
Furthermore, for $n \ge 2$,
\begin{equation} \label{growth3} 2 \prod_{j=0}^{n-2}(2^j +1) < W(n) < \prod_{j=0}^{n-1} (2^j+1). \end{equation}
\end{proposition}
\begin{proof} The first inequality in (\ref{growth1}) arises as follows.
$$ W(n) = \sum_{k=0}^{2^{n-1}} A(n,k) > \sum_{k=2^{n-2}}^{2^{n-1}} A(n,k) = (2^{n-2} + 1) W(n-1). $$
The second inequality arises by using $A(n,k) \le W(n-1)$ for $n$ at least $2$. The double inequality (\ref{growth2}) is immediate from (\ref{growth1}). Multiplying the inequalities in (\ref{growth2}) gives
$$ \prod_{j=0}^{n-2}(2^j +1) < \frac {W(n)} {W(1)} < \prod_{j=0}^{n-2} (2^{j+1}+1) = \prod_{j=1}^{n-1}(2^j +1). $$
Since $W(1)=2$, and $2^0+1=2$, formula (\ref{growth3}) follows.
\end{proof}
\begin{corollary} For $n\ge 2$,
$$ 2 < \frac{W(n)}{ \prod_{j=0}^{{n-2}} (1+2^j)} < 1 + 2^n. $$\end{corollary}
Although the lower and upper bounds in (\ref{growth3}) both define
well-known sequences, they are rather crude for estimating $W(n)$. We
illustrate this for small $n$ in Table~\ref{tab1}.
The left-hand column denotes the lower bound, the middle column gives
the value of $W(n)$, and the right-hand column denotes the upper bound.
\begin{table}[htb]
\begin{center}
\begin{tabular}{ccc}
lower bound & $W(n)$ & upper bound \\
\hline
4 & $W(2)= 5$ & 6 \\
12 & $W(3)=19$ & 30 \\
60 & $W(4)=123$ & 270 \\
540 & $W(5) = 1457$ & 4590 \\
9180 & $W(6)= 32924$ & 151470
\end{tabular}
\end{center}
\caption{Lower and upper bounds.}
\label{tab1}
\end{table}
\newpage
We study several of the ratios occurring in these formulas. The following gives a sense of the growth of the ratios of consecutive $W(N)$:
\begin{itemize}
\item $ \frac{W(2)}{W(1)} =\frac{5}{ 2} = 2.5$
\item $ \frac {W(3)}{W(2)} =\frac {19} {5} = 3.8 \ldots$
\item $ \frac{W(4)}{W(3)} =\frac{123} {19} = 6.473 \ldots$
\item $ \frac{W(5)} {W(4)} = \frac{1457 } {123} = 11.845 \ldots $
\item $ \frac{W(6)}{ W(5)} =\frac{32924} {1457} = 22.597 \ldots$
\item $\frac{W(7)} {W(6)} = \frac {1452015}{32924} = 44.102 \ldots$
\end{itemize} Inequality (\ref{growth1}) implies that the ratio slightly less than doubles at each stage.
The following gives a sense of how accurate it is to include only the easily computed terms, namely those equal to $W(n-1)$. Let $m(n)$ denote the sum of these terms. For small $N$ they compute approximately three quarters of the valid brackets. Asymptotically they seem to compute about $.744$ of the valid brackets. See Example \ref{asymp} for a bit more discussion. Thus the lower bound provides useful information.
\begin{itemize}
\item $ \frac{ m(2)}{ W(2)} = \frac{4}{ 5} = .800$
\item $ \frac{m(3)} {W(3) } = \frac{15 }{19} = .7894 \ldots$
\item $ \frac{m(4)} {W(4)} = \frac{ 95} {123} = .7723 \ldots$
\item $ \frac{m(5)} {W(5)} = \frac{ 1107} {1457} = .7597 \ldots$
\item $ \frac{m(6)}{ W(6)} = \frac{24769}{ 32924} = .7523 \ldots$
\item $\frac {m(7)}{W(7)} = \frac { 33* 32924} {1452015} = .748264 \ldots$
\end{itemize}
Put $M(N) = \prod_{j=0}^{N-1} (1+2^j)$. This sequence of upper bounds appears as sequence \seqnum{A028361} in \cite{OEIS}.
The ratio $\frac{W(N)}{M(N)}$ tends to $0$ as $N$ increases, although we leave a proof to the interested reader.
\begin{itemize}
\item $ \frac{W(1)}{M(1) } = \frac{2}{ 2} = 1$
\item $\frac{W(2)}{M(2)} = \frac{5}{6} = .833 \ldots$
\item $\frac {W(3)}{ M(3)} = \frac{19}{30} = .633 \ldots$
\item $\frac{ W(4)}{ M(4)} =\frac {123} {270} = .455 \ldots$
\item $\frac{W(5)}{M(5)} = \frac{1457}{ 4590}=. 317 \ldots$
\item $\frac{W(6)}{M(6)} = \frac{32924}{151470}= .217 \ldots$
\end{itemize}
\section{Concluding comments}
\label{four}
Consider a tournament with $N$ rounds. A contestant picks all the games before any are played. After the games are played, we wish to evaluate these picks.
To do so, we regard the contestant's picks as an $N$-tuple, which we call a
{\it valid bracket}. The main point of this paper is to ask how many valid brackets $W(N)$ there are. The answer is quite subtle.
The number $A(N,k)$ is defined to be the number of valid $N$-tuples for which $x_1=k$, and $W(N)$ is the sum over $k$ of these numbers. In Proposition \ref{recurrence} we established a double recurrence for
computing the $A(N,k)$. We found polynomial expressions for these numbers. We regard the $A(N,k)$ as an infinite matrix ${\mathcal A}$.
The numbers $W(N)$ grow rapidly with $N$ and turn out to be difficult to compute.
In Section~\ref{three} we provided upper and lower bounds for this sequence.
\begin{remark} \label{remark2} One can obtain a deeper understanding of this sequence $W(N)$
in the following way. There are four types of entries in the $N$-th row of ${\mathcal A}$; for $k > 2^{N-1}$ the entries are all $0$. We can ignore these! For certain values of $k$, all the entries equal $W(N-1)$.
For certain smaller values of $k$, each entry is easily expressed as $W(N-1) - m W(N-2)$ for some integer $m$. The sum of all these terms is relatively easy to compute in terms of previous values.
The entries for smaller $k$ are harder to compute.
It is possible to determine, asymptotically, the fraction of $W(N)$ that is realized by each of these three types of terms; one can then use this result to
give additional asymptotic information on the ratio $\frac {W(N)} {W(N-1)}$, for example. We omit this discussion, as considerable details are required, and we prefer keeping the paper accessible.
\end{remark}
\begin{example} \label{asymp} Put $N=6$. The entries $A(6,k)$ appear just before Proposition \ref{polynomial1}. We work from the right.
There are seventeen copies of $1457$. The total of these terms is $24769$. The next collection consists of the numbers $350, 473, 596, \ldots, 1334$. These sum to $7578$.
The remaining group of terms is given by $1,6,20,48,95,161,246$. These sum to $577$. Thus
$$ W(6) = 32924 = 24769 + 7578 + 577.$$
The part of $W(6)$ contributed by $24769$ is about $.752$. The part contributed by $7578$ is about $.230$. The part contributed by $577$ is about $.0175$.
Asymptotically these fractional parts are all non-zero, with values about $.74$, $.24$, and $.02$. Note that the largest is a bit smaller than $\frac{3}{4}$.
\end{example}
\begin{remark} The sequence $M(N)$ of upper bounds is sequence
\seqnum{A028361} in \cite{OEIS}.
As noted in the introduction, the sequence $W(N)$ is
\seqnum{A355519} in \cite{OEIS}.
\end{remark}
\section{Acknowledgments}
The author acknowledges fruitful discussions with Doug West, Renming Song, Paul Newton, and Carl Jockusch.
The author particularly thanks Dan Putnam for some coding that corroborates the results here.
The author and Newton \cite{DN} have been developing methods to evaluate brackets.
It is of course useful there to have an idea of the size of the problem for a tournament with $N$ rounds, although most of the interest lies in the special case $N=6$ for the college basketball tournament.
The author also thanks an unnamed referee for finding several typos, for comments on where more detail would be useful, and for suggesting some reordering of the material.
The author hopes that these improvements make the paper widely accessible.
\begin{thebibliography}{4}
\bibitem{DN} John P. D'Angelo and Paul K. Newton, Bracket evaluation, preprint.
\bibitem{P} Dan Putnam, Personal communication.
\bibitem{OEIS} N. J. A. Sloane et al.,
{\it The On-Line Encyclopedia of Integer Sequences}, 2022.
Available at \url{https://oeis.org}.
\bibitem{W} Douglas B. West, {\it Combinatorial Mathematics}, Cambridge University Press, 2022.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2020 {\it Mathematics Subject Classification}:
Primary 11B83, Secondary 11B37.
\noindent \emph{Keywords: }
integer sequence, combinatorial polynomial, recurrence relation, bracket tournament.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A028361} and
\seqnum{A355519}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received April 19 2022;
revised versions received July 4 2022; July 5 2022.
Published in {\it Journal of Integer Sequences}, July 27 2022.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}