Contar estructuras multidimensionales (estados del juego Chomp)

El juego Chomp se describe de la siguiente manera en Wikipedia :

Chomp es un juego de estrategia para 2 jugadores que se juega en una "barra de chocolate" rectangular formada por bloques cuadrados más pequeños (celdas rectangulares). Los jugadores se turnan para elegir un bloque y "comerlo" (retirar del tablero), junto con los que están debajo y a su derecha. El bloque superior izquierdo está "envenenado" y el jugador que se lo come pierde.

Estoy interesado en contar la cantidad de posibles estados del juego, incluido el estado inicial del juego donde queda todo el chocolate y el estado final del juego donde todo el chocolate se ha ido.

$2$-dimensiones

En el caso bidimensional, esto es posible usando la siguiente observación:

Visualizaremos un tablero de juego de la siguiente manera:

$$\begin{array}{|c|c|c|c|}\hline x & x & x & x\\ \hline x & x & x & x\\ \hline x & x & x & -\\ \hline -& - & - & -\\ \hline \end{array}$$

dónde$x$denotan los bloques restantes, y el$-$corresponde a bloques eliminados. Cualquier estado de juego bidimensional se caracteriza por las celdas en el límite de las celdas restantes (las celdas que son adyacentes, ya sea directa o diagonalmente, a una celda eliminada o al lado inferior o derecho del tablero). Estos son algunos ejemplos de estados del juego, con celdas de límite resaltadas

$$\begin{array}{|c|c|c|c|}\hline x & x & x & {\bf x}\\ \hline x & x & {\bf x} & {\bf x}\\ \hline {\bf x} & {\bf x} & {\bf x} & -\\ \hline -& - & - & -\\ \hline \end{array} \quad \begin{array}{|c|c|c|c|}\hline x & x & x & {\bf x}\\ \hline x & x & x & {\bf x}\\ \hline x & x & x & {\bf x}\\ \hline {\bf x} & {\bf x} & {\bf x} & {\bf x}\\ \hline \end{array} \quad \begin{array}{|c|c|c|c|}\hline - & - & - & -\\ \hline - & - & - & -\\ \hline - & - & - & -\\ \hline - & - & - & -\\ \hline \end{array} \quad \begin{array}{|c|c|c|c|}\hline x & {\bf x} & {\bf x} & -\\ \hline x & {\bf x} & - & -\\ \hline {\bf x} & {\bf x} & - & -\\ \hline {\bf x} & - & - & -\\ \hline \end{array}$$

A su vez, dicho límite corresponde a un recorrido especial en el gráfico de cuadrícula construido dejando que cada celda sea un vértice y uniendo los vértices correspondientes a las celdas adyacentes (observe que el estado final corresponde al recorrido vacío). Estas caminatas comienzan en la columna más a la izquierda del gráfico de cuadrícula y terminan en la fila superior del gráfico de cuadrícula. Usando esta biyección de los estados del juego a tales caminatas, calculamos el número de estados del juego de la siguiente manera: El número de estados del juego en un juego bidimensional de chomp con$n_1$filas y$n_2$columnas está dada por

$$1 + \sum_{d_1 = 1}^{n_1} \sum_{d_2 = 1}^{n_2} \binom{d_1 + d_2 - 2}{d_1-1}.$$

que se basa en el número de pasos de escalera .

El más uno se encarga del estado final del juego. Por ejemplo, enchufar$n_1=n_2=2$Nos da

$$1 + \sum_{d_1 = 1}^{2} \sum_{d_2 = 1}^{2} \binom{d_1 + d_2 - 2}{d_1-1} = 1 + \binom{0}{0} + \binom{1}{0} + \binom{1}{1} + \binom{2}{1} + = 6$$

que corresponde a los estados del juego

$$\begin{array}{|c|c|}\hline x & x\\ \hline x & x\\ \hline \end{array} \quad \begin{array}{|c|c|}\hline x & x\\ \hline x & -\\ \hline \end{array} \quad \begin{array}{|c|c|}\hline x & -\\ \hline x & -\\ \hline \end{array} \quad \begin{array}{|c|c|}\hline x & x\\ \hline - & -\\ \hline \end{array} \quad \begin{array}{|c|c|}\hline x & -\\ \hline - & -\\ \hline \end{array} \quad \begin{array}{|c|c|}\hline - & -\\ \hline - & -\\ \hline \end{array}$$

$\geq 2$-dimensiones

Ahora mi pregunta es, ¿cómo contamos la cantidad de estados de juego para juegos de chomp con dimensión$\geq 2$? ¿Se generaliza la idea de los caminos más cortos en el gráfico de red multidimensional? ¿Existe una fórmula cerrada simple para el número de posiciones de juego de Chomp en un$k$-juego dimensional de tamaño$n_1 \times \ldots \times n_k$? ¿Qué pasa con el caso simple de un$k$-juego dimensional de tamaño$2 \times 2 \times \ldots \times 2$?