Tic-Tac-Toe

Note that two tic-tac-toe games are considered distinct even if they arrive at the same final board, provided the moves are played in different orders. If you allowed both players to keep playing after someone gets 3 in a row, there'd be $9!$ games (9 places for the first X, 8 places for the first O, 7 places for the second X, etc.).

For each $N<9$ , we need to add in $M_N$ incomplete boards to our total, and subtract $(9-N)!\times M_N$ completed boards that, in fact, are not valid games (since someone already won). You can think of this as, for each of the $M_N$ games, there are $9-N$ spots left on the board; there are $(9-N)!$ ways to fill those spots.

$\begin{aligned} \text{Number of games} &= 9! + M_5 - 4!M_5 + M_6-3!M_6 + M_7-2!M_7 + M_8 - 1!M_8 \\ &= 9! + M_5-24M_5 + M_6 - 6M_6 + M_7-2M_6 + M_8 - M_8 \\ &= \boxed{9! - 23M_5 - 5M_6 - M_7} \end{aligned}$

Rather than O and X imagine someone completing the grid by adding consecutive numbers 1, 2, 3 ... 9. There are 9! different ways to do this. When treated as a game, the process will stop (and the grid potentially remain incomplete) if there are ever 3 odd numbers or 3 even numbers in a row.

We can analyse the 9! possibilities as follows: Some will end in a draw (D). Some will end with a full grid on the ninth move ( $M_9$ ). Some will end on the eighth move, but there is only one empty spot for number 9, so there are $M_8$ such possibilities. Some will end on the seventh move, in which case there are two possible ways to complete the grid with the final 8 and 9. Hence this represents $2M_7$ of the 9! possibilities. Similarly any game which ends on the sixth move would leave 3! ways to complete the grid with 7, 8 and 9 (hence $6M_6$ ). Finally any game ending on the fifth move corresponds to 4! different 'completed' grids (hence $24M_5$ ). There are no games which will end in four or less moves.

So 9! = $D + M_9 + M_8 + 2M_7 + 6M_6 + 24M_5$

The total number of games $= M_5 + M_6 + M_7 + M_8 + M_9 + D = \boxed{9! - M_7 - 5M_6 - 23M_5}$

9! Is wrong as many games end before the 9th move. Some games require only 5 moves, only one response has an answer that includes 5 move game, so I picked that.

This page gives all the details, with the exact values of $M_5$ , $M_6$ , $M_7$ , $M_8$ and $M_9$ , if you want to know them!