I wanted to know how many possible legal positions of tic-tac-toe can be found if we ignore symmetry. I have done a little calculation myself but the answers i have found in the internet are way larger than mine. Can someone please check if my calculations are correct?
My Answer:
For move $1$ , There are 9 squares to place 1 object; (O or X doesn't matter)
So , Total positions = $9$
For move $2$, There are 9 squares to place 2 objects;
So, Total positions= $^9P_2 = 72$
For move $3$, We have to place 3 objects in 9 squares, but 2 of them are same;
So, Total Positions=$\frac{^9P_3}{2!}= 252$
For move $4$, It will be 4 objects but of 2 types; So, Total positions= $\frac{^9P_4}{2!2!}= 756$
In this method we can work out the rest as well:
Move $5= \frac{^9P_5}{3!2!}= 1260$
Move $6= \frac{^9P_6}{3!3!}= 1680$
Move $7= \frac{^9P_7}{4!3!}= 1260$
Move $8= \frac{^9P_8}{4!4!}= 1630$
Move $9= \frac{^9P_9}{5!4!}= 126$
In total, $$\sum_{i=1}^{n=9} \frac{^nP_i}{\left\lfloor\frac{i}{2}\right\rfloor!\left\lceil\frac{i}{2}\right\rceil!} = (9+72+252+756+1260+1680+1260+1630+126) = 6045$$
Is my answer correct? Is there anything wrong in my calculations? I came up with the equation for the sum by looking at the trend of the positions in each move. Is the equation correct?