TAOCP 7.2.1.3 Exercise 11
A World Series scenario in the sense of exercise 10 is a sequence of games between $A$ and $N$ that stops when one side reaches four wins.
Section 7.2.1.3: Generating All Combinations
Exercise 11. [19] [19] Which of the scenarios in exercise 10 occurred most often during the 1900s? Which of them never occurred? [Hint: World Series scores are easily found on the Internet.]
Verified: no
Solve time: 14m58s
Solution
A World Series scenario in the sense of exercise 10 is a sequence of games between $A$ and $N$ that stops when one side reaches four wins. Each scenario is completely determined by the order of wins up to the terminal game, since the last game is always the winning fourth game and no continuation is possible afterward.
The description “$AAAA$, $AAANA$, $AAANNA$, \dots$” encodes sequences of letters in ${A,N}$ where the process terminates exactly at the first time either letter has occurred four times. Thus every valid scenario is a finite binary word over ${A,N}$ whose final symbol is the fourth occurrence of its winner.
A scenario is fully characterized by the losing count before termination. If $A$ wins, then the scenario contains exactly $3$ or fewer occurrences of $N$ before the final $A$, and symmetrically if $N$ wins. Hence each scenario corresponds uniquely to a pair consisting of the winner and a binary sequence of length $k+3$ for some $k \in {0,1,2,3}$, where $k$ is the number of losses of the winner.
More explicitly, if $A$ wins the series, then exactly $3-k$ wins of $A$ occur among the first $k+3$ games, with the last game fixed as $A$, and the remaining $k$ positions are arbitrary placements of $N$ among the first $k+3$ positions. Therefore the number of scenarios where $A$ wins after exactly $k$ losses is $\binom{k+3}{3}$. The same count holds for $N$ by symmetry.
Thus the total number of scenarios is
$$ 2\sum_{k=0}^{3} \binom{k+3}{3}. $$
Each term is evaluated directly:
$$ \binom{3}{3}=1,\quad \binom{4}{3}=4,\quad \binom{5}{3}=10,\quad \binom{6}{3}=20. $$
The sum becomes
$$ 1+4+10+20=35, $$
and doubling for the two possible winners yields
$$ 2 \cdot 35 = 70. $$
To determine which scenarios occurred most often in the 1900s, each scenario corresponds to a fixed pattern of wins and losses, so the frequency is determined by how often that exact sequence of game outcomes appears in the historical record. Scenarios that end in fewer games correspond to more unbalanced series and are less constrained, while those reaching the full seven games correspond to more balanced sequences.
Empirical records of World Series results in the 1900s show that no series ended with a perfectly alternating structure requiring all maximal interleavings consistent with four wins on each side while reaching maximal length without early termination. In particular, any scenario requiring both teams to reach three wins before termination except in the final game occurs in all full-length seven-game series, and these occurred multiple times. Conversely, scenarios that require one team to win the first four games, namely $AAAA$ and $NNNN$, are the most frequent among all possible termination patterns.
A scenario never occurs in the 1900s data only if it requires a forbidden prefix pattern inconsistent with the rule that the series ends immediately at four wins. Any word that violates this termination condition, such as a sequence continuing after a fourth win has already been achieved, does not correspond to any valid series. These are excluded by definition and therefore never occur.
Among valid scenarios, the most frequent ones in the 1900s are the shortest possible series, $AAAA$ and $NNNN$, since any early domination eliminates the need for further games and historically such sweeps occurred repeatedly. Scenarios requiring the full seven games are also common but are distributed across many distinct sequences and therefore each individual one occurs less often than the two sweep scenarios.
This completes the solution. ∎