This question was originally posed on math.SE but seems to require research-level mathematics expertise:
Two players play each other in a match of games of chess where the match winner is the first to achieve either $m>0$ total game wins or $0<n<m$ game wins in a row. (There are no ties.) How many distinct possible sequences of game results exist as a function of $n$ and $m$?
For small values, one can write out the sequences (as in the linked question).
Clearly the shortest sequence of games is of length $n$ (of which there are two) and longest sequence of games is of length $2 m - 1$, but we seek the total number of distinct sequences.
First steps
Assume, without loss of generality, that the winning player is $A$ and the loser is $B$.
Let $0<k \leq 2m-1$ be the length of a sequence. If $k<n$ there is no match winner; we can ignore such cases.
There are, then, two ranges of interest:
- $n \leq k < m$
- $m \leq k \leq 2m -1$
In the first case, the only way $A$ wins the match is to win $n$ games in a row. Of course the last game (position $k$) $A$ wins, terminating the match. Thus the final $n$ games $A$ must win. That leaves $k-n$ preceding "other" slots. The last one of these must be won by $B$. Thus there are $k - n - 1$ remaining "unassigned" slots which can be won in any order so long as $A$ does not win $n$ in a row.
The number of ways this can be achieved is:
$$\sum\limits_{j=0}^{k-n-1} {k-n-1 \choose j}$$
but again, this over counts in certain cases because it includes cases in which $A$ wins $n$ consecutive games.
In the second case there are two categories of ways $A$ wins: by winning $m$ games or by winning $n$ in a row. In either of these cases, the last game (slot $k$) $A$ must win. If $A$ wins $m$ total games (on the $k$th game) then $A$ has won $m-1$ games in the $2m - 2$, and that means that $B$ has won the remaining $m-1$ games (but neither have won $n$ in a row).
The total number of ways this can be done is:
$$\sum\limits_{j=0}^{m-1} {2m - 2 \choose j}$$
but note that some of these cases may have $A$ win $n$ in a row. We must subtract those cases.
Another way to view part of the problem
Perhaps we can view this problem as a path through a lattice graph. Consider the number of sequences in which $A$ wins the match by winning $m$ games (and not by winning $n$ in a row). Each game won by $A$ is a lattice step to the right and each game won by $B$ is a step upward. Let's assume $A$ will be the winner. Thus the terminal nodes are those on the right-most column of the graph, $m$ steps horizontally.
Each path with be an alternating sequence of "streaks" of winning alternating by $A$ then $B$ then $A$... However, each of these streaks can be only of length $1, 2, \ldots, n-1$.
So here we have $m=15$ and $n=4$. Each streak is of length less than $4$.
Each set of streaks of the winner $A$ represent an integer partition of $m$ restricted to elements $1, 2, \ldots, n-1$. (This is not the case for $B$, whose sum must be less than $m$ because $B$ loses.)
So the question can be restated as finding the number of distinct sequences of integer partitions of $m$, and for each such distinct sets of "streaks." Then, we find the number of integer partitions for $B$ that have the same number of streaks, or one greater or one less. Then we can alternate a streak for $A$ with a streak for $B$, and so on.
Counting this total number should give the number of sequences (paths) in which $A$ wins by reaching $m$ won games (but not having a streak of $n$).
Of course, this is not the full solution to the problem... but perhaps a casting that will help.