Coloring the faces of a hypercube

First let's state the special case of Burnside's lemma that is relevant here.

Lemma: Let $G$ be a finite group acting on a finite set $X$. The number of ways to color the elements of $X$ with $z$ different colors, up to the action of $G$, is

$$\frac{1}{|G|} \sum_{g \in G} z^{c(g)}$$

where $c(g)$ is the number of cycles in the cycle decomposition of $g$ acting on $X$. (Proof.)

Here $X$ is the set of faces of a hypercube. In $n$ dimensions there are $2n$ such faces. $G$ is the subgroup of index $2$ in the hyperoctahedral group with determinant $1$, also known as the Coxeter group $D_n$. So our job now is to count, for each $k$, the number of elements of $D_n$ with $k$ cycles in the action on $X$.

Now, note that to analyze the action of $D_n$ on the faces it suffices to analyze the action of $D_n$ on the midpoints of the faces. But these are precisely the $2n$ points $(0, 0, ... \pm 1, ..., 0, 0)$, so writing the elements of $D_n$ as signed permutation matrices is very well-suited to analyzing their action on these points; in particular, it suffices to figure out the answer for a single signed cycle. But this turns out to be very simple: there are either one or two cycles depending on whether the product of the signs is $-1$ or $+1$.

(It might be helpful here to play with a specific example. Consider $\left[ \begin{array}{cc} 0 & 1 & 0 \\ 0 & 0 & -1 \\ -1 & 0 & 0 \end{array} \right]$ acting on the six points $(\pm 1, 0, 0), (0, \pm 1, 0), (0, 0, \pm 1)$ to get a feel for what's going on in the general case.)

From here I think it's easiest to work with generating functions because the combinatorics get a little messy. Begin with the identity

$$\sum_{m \ge 0} Z(S_n) t^n = \exp \left( z_1 t + \frac{z_2 t^2}{2} + \frac{z_3 t^3}{3} + ... \right)$$

where $Z(S_n)$ is the cycle index polynomial for the action of $S_n$ on $\{ 1, 2, ... n \}$. Each $z_i$ is the term that controls cycles of length $i$. We want to modify this generating function so that it tells us how the cycles in $D_n$ work. There are $2^i$ signed cycles of length $i$ which come in two flavors: half of them have positive sign product (two unsigned cycles) and half of them have negative sign product (one unsigned cycle), so to keep track of the total number of unsigned cycles we should replace $z_i$ with $2^{i-1} z^2 + 2^{i-1} z$. We also have to keep in mind that the determinant of a signed cycle is its sign product multiplied by $(-1)^{i+1}$, and we only want permutations with determinant $1$. So the generating function we want is

$$\sum_{n \ge 0} f_n(z) \frac{t^n}{n!} = \frac{1}{2} \left( \exp \left( \sum_{i \ge 1} \frac{2^{i-1} z^2 + 2^{i-1} z) t^i}{i} \right) + \exp \left( \sum_{i \ge 1} (-1)^{i+1} \frac{2^{i-1} z^2 - 2^{i-1} z) t^i}{i} \right) \right)$$

where $f_n(z) = \sum_{g \in D_n} z^{c(g)}$. After some simplification the above becomes

$$\sum_{n \ge 0} \frac{1}{|D_n|} f_n(z) t^n = \frac{1}{(1 - t)^{(z^2+z)/2}} + (1+t)^{(z^2-z)/2}.$$

Substituting $z = 2$ gives, at last, the answer

$$\sum_{n \ge 0} \frac{1}{|D_n|} f_n(2) t^n = \frac{1}{(1 - t)^3} + 1 + t.$$

In other words, for $n \ge 2$ we simply have $\frac{1}{|D_n|} f_n(2) = {n+2 \choose 2}$. This is such a simple answer that there should be a direct proof of it. I'll keep working on it. (There is a rather straightforward proof of the corresponding result with "hypercube" replaced by "simplex," so my guess is something along those lines is possible here.)

Once someone else has done the hard work and come up with the answer, as Qiaochu has done, then it's easy to prove it on an ad hoc basis as this interloper (me) will do.

Consider an $n$-cube with faces coloured red and blue. Consider a set of $n$ balls. Colour the $j$-th ball red, blue or green according to the colours of the $j$-th pair of faces in the cube, that is if they both have the same colour give the ball that colour, else if they have different colours colour the ball green. Now a symmetry operation on the cube will shuffle the balls so the number of each colour of balls will be the same. Conversely given the $n$ coloured balls there will be various coloured cubes giving rise to the colour distribution of the balls, but these will all be equivalent under the full symmetry group of the cube. However for $n\ge 2$ each $2$-coloured cube has a non-rotational symmetry, so any two coloured cubes giving rise to the same colour distribution of balls are related by a rotation. Hence the number of $2$-coloured $n$-cubes up rotation is the same as the number of triples $(r,b,g)$ of nonnegative integers adding to $n$ and there are ${n+2\choose 2}$ of these.

One can repeat this with $k$-colours for the cube. This time one needs ${k+1\choose 2}$ colours for the balls, and the argument ensuring that rotations and the full symmetry group give the same answer requires $n>{k\choose 2}$ (why?).

Added (30/9/2010) One can get the general result using these considerations. For $n>{k\choose 2}$ one gets $${n+(k^2+k)/2-1\choose (k^2+k)/2-1}$$ colourings up to rotations. For $n\le {k\choose 2}$ there are $k$-colourings having no improper (determinant $-1$) symmetries. But any such colouring has no nontrivial symmetries at all. If two opposite faces have the same colour, one can reflect through a hyperplane parallel to them. So assume that no colour is opposite itself. Then if two pairs of opposite faces have the same two colours between them, one can reflect in a plane $x_i=x_j$or $x_i=-x_j$. Hence in these "special" colourings each pair of opposite faces has a distinct pair of distinct colours. Up to symmetry there are $${(k^2-k)/2\choose n}$$ of these special colourings. So for $n\le{k\choose 2}$ there are $${(k^2-k)/2\choose n}+{n+(k^2+k)/2-1\choose (k^2+k)/2-1}$$ up to rotational symmetries.

I presume you want to colour the faces of the cube? If so there are $2^6$ colourings as there are six faces. But do you want two colourings which are equivalent under rotations (or rotations and reflections) to count as as the same? If so then this is a classic application of Burnside's lemma.

Added If you want to do the same in higher dimensions then you need a good handle on the symmetries of an $n$-cube. Its convenient to centre the cube at the origin and take its vertices to be all points $(\pm1,\ldots,\pm1)$. Then all symmetries of the cube fix the origin and their matrices are "signed" permutation matrices: each row and column is all zero save for one entry which is $\pm1$. The rotations correspond to signed permutation matrices of determinant 1. The faces are the sets defined by $x_i=1$ and $x_i=-1$. Again use Burnside's lemma but the book-keeping gets fiddlier.