¿Cuántos tableros de juego posibles (estados del juego) de tic tac toe n x n son posibles?

Question

Si tengo un tablero de tamaño n x n en tic tac toe y he utilizado un campo para poner una cruz como la siguiente

 | | | |
--------
 | | | |
--------
 | | | |
--------
 | | |X|

Cuántos tableros posibles hay en esta partida -> Me refiero a todos los finales posibles de esta partida. Por ejemplo en la siguiente jugada hay 15 posibles tableros en la siguiente jugada hay 14 pero derivan de esos 15 tableros, entonces es $n!$ posibles tablas en las que $n$ ¿es el número de campos vacíos?

El juego termina cuando: los tableros están llenos o hay n figuras iguales en una línea.

Edición 2: Si es muy difícil, ¿podemos estimar el orden de magnitud? ¿Límite por abajo y por arriba (notación small o big O)?

Edición3 La estimación de arriba sería calcular todos los estados del juego si terminamos el juego cuando el tablero está lleno.

Answer 1

Hay un total de $n^2$ plazas a rellenar. Si se inicia la cruz, el número de cruces es $\tfrac{1}{2}n^2$ si $n$ es par, o $\frac{1}{2}(n^2+1)$ si $n$ es impar. El resto son círculos, por lo que el número de tablas llenas es $$\frac{(n^2)!}{\left(\left(\tfrac{n^2}{2}\right)!\right)^2}\qquad\text{or}\qquad\frac{(n^2)!}{\left(\frac{n^2-1}{2}\right)!\left(\frac{n^2+1}{2}\right)!},$$ dependiendo de si $n$ es par o impar. Esto no es un límite superior muy agudo.

Por otro lado, para que un juego termine, la cruz debe hacer al menos $n$ movimientos, y por lo tanto el círculo debe hacer al menos $n-1$ movimientos. El número de formas de hacerlo es $$\frac{(n^2)!}{n!(n-1)!(n-1)^2!},$$ por lo que hay al menos esta cantidad de formas distintas de terminar, y esto no es un límite inferior muy agudo.