# Counting multidimensional structures (Chomp game states)

The game Chomp is described as follows on Wikipedia:

Chomp is a 2-player game of strategy played on a rectangular "chocolate bar" made up of smaller square blocks (rectangular cells). The players take it in turns to choose one block and "eat it" (remove from the board), together with those that are below it and to its right. The top left block is "poisoned" and the player who eats this loses.

I am interested in counting the number of possible game states, including the initial game state where all the chocolate is left, and the end-game state where all the chocolate is gone.

## $2$-dimensions

In the 2-dimensional case, this is possible using the following observation:

We will visualise a game board as follows:

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

where $x$ denote the remaining blocks, and the $-$ corresponds to removed blocks. Any 2-dimensional game state, is characterised by the cells on the boundary of the remaining cells (the cells which are adjacent - either directly or diagonally - to a removed cell or the bottom or right side of the board). Here are some examples of game states, with boundary cells highlighted

$$\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}$$

In turn, such a boundary corresponds to a special walk on the grid graph constructed by letting each cell be a vertex, and by joining vertices corresponding to adjacent cells (note that the end-state corresponds to the empty walk). These walks start in the left-most column of the grid graph, and end in the top row of the grid graph. Using this bijection from game states to such walks, we compute the number of game states as follows: The number of game states in a 2-dimensional chomp-game with $n_1$ rows and $n_2$ columns is given by

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

which is based on the number of staircase walks.

The plus one takes care of the end-game state. For example, plugging in $n_1=n_2=2$ gives us $$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$$

which corresponds to the game states $$\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$-dimensions

Now my question is, how do we count the number of game states for chomp games with dimension $\geq 2$? Does the idea of shortest paths on the multidimensional lattice graph generalise? Is there a simple closed formule for the number of Chomp game-positions in a $k$-dimensional game of size $n_1 \times \ldots \times n_k$? What about the simple case of a $k$-dimensional game of size $2 \times 2 \times \ldots \times 2$?

-
Have you tried calculating some small examples and looking up the results in the Online Encyclopedia of Integer Sequences? Or just type "chomp" into the site - it comes up with 25 sequences. I haven't checked to see if they include what you want. –  Gerry Myerson Sep 28 '12 at 5:52
I have not been able to find anything on oeis. I have found the number of $2 \times 2 \times 2$ games, to be equal to 20. –  utdiscant Sep 28 '12 at 6:12
In the two-dimensional case, I think you're counting Young diagrams, see en.wikipedia.org/wiki/Young_tableau I would not be surprised to find that work has been done on generalizing Young diagrams to higher dimensions. –  Gerry Myerson Sep 28 '12 at 6:25
Isn't you some for the two-dimensional case equal to $\binom{n_1 + n_2}{n_1}$? I think, you can see it if you add a leftmost column and a top row and count the staircase walks from left bottom to right top corner. –  martini Sep 28 '12 at 7:27
@martini Nicely spotted, you are absolutely correct. This makes me believe in a simple formula for the $d$-dimensional case even more. –  utdiscant Sep 28 '12 at 7:50

If $C_n$ is a linear order with $n$ elements, each state in the $n_1\times n_2\times\ldots\times n_m$ game is uniquely determined by an antichain in the product partial order $C_{n_1}\times C_{n_2}\times\ldots\times C_{n_m}$. The number of antichains in $C_2^m$ is the $m$-th Dedekind number, which is known explicitly only for $0\le m\le 8$:
$$2,3,6,20,168,7581,7828354,2414682040998,56130437228687557907788$$
The Wikipedia article gives a (fairly useless!) exact formula that is a summation of $2^{2^m}$ products and some asymptotic results. This is OEIS A000372, where more references can be found. The generalized Chomp problem seems likely to be at least as intractable, despite the nice result for $m=2$.