I understand there are numerous questions around the internet about the state space of tic-tac-toe but I have a feeling they've usually got it wrong. Alternatively, perhaps it is I who have it wrong. Which is what leads me to my question.
Common Over Estimates:
Over Estimate One:
First some common answers to the number of possible states in Tic-Tac-Toe:
$9! = 362880$
This is one solution, which is overstates the upper-bound by the most I have seen, as it includes states such as:
x1|x2|x3
--------
x4|x5|x6
--------
x7|x8|x9
This solution also includes the case were x1 and x2 are reversed, and all the other combinations of just X's on the board.
###Over Estimate Two:
Another common answer that is better, common, but still over-estimating is:
$3^9 = 19683$
Which is better. Now we only count the following board once...
x|x|x
-----
x|x|x
-----
x|x|x
but I've still never heard of any type of one-player tic-tac-toe and it seems boring.
These guys claim they've got the answer but they are discussing games not state-spaces. That is the progression of the N-moves in a game is also taken into account.
The Power of Choose:
After sitting down and thinking for awhile I came up with a formula that does a more precise job at estimating the state space of tic-tac-toe and it is quite simple, but still not 100% as it still overestimates.
$9 \choose 1$ * $8 \choose 0$ +
$9 \choose 1$ * $8 \choose 1$ +
$9 \choose 2$ * $7 \choose 1$ +
$9 \choose 2$ * $7 \choose 2$ +
$9 \choose 3$ * $6 \choose 2$ +
$9 \choose 3$ * $6 \choose 3$ +
$9 \choose 4$ * $5 \choose 3$ +
$9 \choose 4$ * $5 \choose 4$ +
$9 \choose 5$ * $4 \choose 5$ = 9+72+252+756+1260+1680+1260+630+126 = 6045
Essentially each term of $9 \choose X$ is placing the X's on the board, then the $K \choose L$ is the O's choosing the appropriate number of places from the remaining open spaces on the board. Each term being added is the number of states being generated at each turn. So for turn 1 we have 9 states, for turn 2, 72 states and so on.
The main point here is 6045 is far fewer than the other estimations, the use of Choose seems rather elegant considering its simplicity and the accuracy we are able to achieve, and lastly I like how each term being added correlates to each turn.
I recognize that it is not perfect, as I am ignoring some win conditions, i.e. this board is also counted:
x|x|x
-----
x|o|o
-----
x|o|o
Which isn't a legitimate board but still 6045 is less than $1/3$ of the commonly stated $3^9$ and isn't the equation rather beautiful?
The Question:
The question is, does this application of choose accurately represent how X's and O's can alternatively be placed on a 3x3 grid? Have I missed anything?
Bonus question: Any insights on how to estimate the number of illegitimate boards during moves 6, 7, 8, and 9? Note: With 5 or fewer moves, all boards generated are legitimate.
Clarifying Edit: The goal is not to have a computer brute force the thinking for us, but to gain a deeper understanding of the distribution of win conditions. Also to make sure I didn't make any mistakes.
