Partially-complete tournament brackets This question is with regard to a single-elimination tournament of 16 teams, like the knockout phase of the world cup, or any single region of March Madness.
It's easy to calculate the total number of completed tournament brackets: there are 15 matches, each of which has 2 possible outcomes, for a total of $2^{15}$ possible (32,768) brackets.
I am interested in calculating the number of distinct valid partially-completed brackets, with validity defined as not advancing a team to round n without first advancing them to round n-1.
An upper bound on this number is $3^{15}$ (14,348,907), representing the idea that for each match, you could either choose to advance team 1, advance team 2, or not advance anyone.
However, the number of possible outcomes for a given match is not always 3: it is dependent upon your choices in the previous round. If you only advanced 1 team to this match, you have only 2 choices (advance that team or advance no one). If you didn't advance anyone to this match, you have only one choice (advance no one).
Can anyone help to calculate the sample space I am describing?
 A: I don't have a closed form solution but have a recurrence relation
that provides the solutions.
Firstly, I arrived at a pair of recurrence relations (in two variables) and from there
eliminated one of the equations to obtain a single recurrence
relation in one variable. However, I don't know which of these is easier to solve.
Let $c_n$ be the number of possible partial draws when the
tournament is $n$ rounds deep. E.g. $n=2$ means $2^2 = 4$ teams,
$n=3$ means $2^3=8$ teams. The recursion comes because $c_n$ can
refer to a whole draw of $n$ rounds or to part of a draw where just
that part has $n$ rounds.
Let $d_n$ be the same as $c_n$ except that we have chosen a team in
a succeeding part of its draw and are therefore not allowed to
choose the "no result" option: you have to choose a team in every
match of this part of the draw.
The counting begins at the final match and works back to Round $1$.
At the final of an $n$-round tournament, we want the value of $c_n$.
At this match, you can choose either "no result", Team A or Team B.
This choice determines the way in which we count the number of
alternatives in each of the two half-draws branching off this final.
If you choose "no result", then both half-draws have unrestricted
choices at the next round (semi-final). i.e. you have $3$ choices
available for each semi-final.
If instead you choose Team $A$ in the final, then for that team's
semi-final, you cannot choose "no result", you have only $2$
choices: Team $A$ or its semi-final opponent (which is possibly
unspecified). For the other half-draw, you have the full 3 choices
because by choosing Team $A$, you have the choice of there having
been a Team $B$ opponent in the final or an unspecified opponent.
So the recurrence relations are:
\begin{eqnarray*}
c_n &=& c_{n-1}^2 + 2c_{n-1}d_{n-1} \\
d_n &=& 2c_{n-1}d_{n-1}
\end{eqnarray*}
First equation:
The $c_{n-1}^2$ term is from the "no result" choice in the final.
Each half-draw from there has $c_{n-1}$ different alternatives.
Multiply them together because we want all combinations from the two
half-draws.
The $c_{n-1}d_{n-1}$ term comes from the Team $A$ choice. The Team
$A$ half-draw then has $d_{n-1}$ alternatives, while the other
half-draw has $c_{n-1}$ alternatives. Again, we multiply them
together to get all combinations from the two half-draws.
We multiply this value by $2$ because, by symmetry, the Team $B$
option for the final has the same count as the Team $A$ option.
The boundary conditions:
\begin{eqnarray*}
c_0 &=& 1 \\
d_0 &=& 1
\end{eqnarray*}
The $n=0$ level is where there is only one team and the only option
is to choose that team (because you can't have empty slots, that is,
"no result", in the team list for the initial round).
The relations give values:
\begin{eqnarray*}
c_0 &=& 1 \\
c_1 &=& 3 \\
c_2 &=& 21 \\
c_3 &=& 945 \\
c_4 &=& 1845585 \\
&\cdots&
\end{eqnarray*}
Some SQL code to do these calculations follows. If you're not
familiar with SQL, I think the logic is pretty transparent anyway:

CREATE FUNCTION dbo.Cnt(@n int, @opt bit)
    RETURNS bigint
AS
BEGIN
    declare @Total bigint

    if @n = 0 begin
        return 1
    end
    set @Total = 0
    if @opt = 1 begin /* Cn rather than Dn */
        select @Total = power(dbo.Cnt(@n-1,@opt), 2)
    end
    select @Total = @Total + 2 * dbo.Cnt(@n-1,1) * dbo.Cnt(@n-1,0)
    return @Total
END

These two recurrence equations are non-linear. I have no solution
for them.
By reducing $d_{n-1}$ down to $d_0$, then using the fact $d_0 = 1$ to eliminate it, we can
convert the pair of equations to a single recurrence relation for
$c_n$:
\begin{eqnarray*}
c_n &=& c_{n-1}^2 + 2^{n} \prod_{i=0}^{n-1}{c_i}
\end{eqnarray*}
Boundary condition: $\qquad c_0 = 1$
I'm unable to solve this too.
I hope this is helpful. Sorry for the long-winded explanation above.
If anyone can solve either of these recurrences that would be great.
