# Number of ways of coloring projected faces of any hypercube

EDIT: This is the concrete problem in its current state:

How many ways are there of separating a figure consisting of $l$ layers of squares with connected vertices (as the one seen in Fig. 5, for which $l=4$) into faces, when one can only create faces between any four vertices along the edges? An attempt is shown in Fig. 6 for $l=3$.

Original question:

If we look at the 2D projection of the outline of a cube

we can choose to see it as a normal person,

or we can choose to view it in a slightly more perverted way (so that the edge between green and orange faces is closest to the viewer):

Note that the number of different ways of seeing the cube corresponds to the number of different ways of completely covering (without overlap) the area of the projection by rectangular faces with four different vertices as corners. For an $n$-cube ($n \geq 2$), let us call this number $C_n$. As we have seen, $C_3=2$ and obviously $C_2=1$.

What is the general expression for $C_n$?

At first, when investigating the $4$-cube, I simply drew the projection of one seen at an angle and started constructing the combination tree (blue indicates that a branching choice was made to color that face - the ones in the same figure as the blue face are the ones that were determined as soon as the one in blue was chosen):

However, this was unsystematic and confusing, so I instead realized (hopefully this is true!)$^\dagger$ that I might as well represent it (and indeed any hypercube, by adding more layers) like this:

Let the edges of a square (as it is seen in Fig. 5) be one layer. There is then $1$ layer for a $2$-cube, $2$ for a $3$-cube, $4$ for a $4$-cube, and in general (since there are $2^n$ vertices in an $n$-cube and $4$ vertices in one layer) $2^{n-2}$ layers for an $n$-cube. The idea is now to find out how many new possibilities each layer introduces. Here are the possibilities for two and three layers (I've excluded the ones not unique under rotation and two adjacent faces with the same color is viewed as one face):

This is where I'm stuck: I'm having a hard time seeing the pattern in that there are two ways of having a total of two "split" faces in the three-layer case (fifth and sixth three-layer structure in Fig. 6), but only one way of having one, three or four split faces.
And even if I knew how to deal with this, the task still seems daunting.

Any help is much appreciated!

$^\dagger$ There may be introduced some extra symmetries when drawing the cube as the "inner" cube in Fig. 4, so that the same object will have less possibilities that are unique under rotation, than when seen as in Fig. 6.
This is an unfortunate choice in drawing style, but I believe that this discrepancy in possibilities (only one unique possibility of coloring the "inner" cube in Fig. 4) can be avoided if we draw the inner cube in Fig. 4 in two- or three-point perspective instead, so that "the front" surface is bigger than the "back" (or, which makes it count as two possibilities again, the other way around).

If that is not the case, however, it will surely be impossible to order all possible scenarios under continuous rotation of any hypercube so as to be able to account for this effect, so let's focus our attention on the problem as it is given from Fig. 6, and not worry about how to interpret the final result. Thanks to David K for pointing this out.

• It seems to me that in this way of doing things, the number of colorings is dependent on perspective. If you had drawn the original cube the way you drew the "inner" cube in figure 4, there would be only one coloring (up to rotation). So I'm not convinced a priori that figure 4 has the same number of colorings as figure 5. – David K Feb 19 '16 at 13:53
• @DavidK .. Can't this discrepancy be avoided simply if we draw the cube in Fig. 4 in perspective (here I mean "perspective" as in "with vanishing points"), so that "the front" surface is bigger than the "back" (or, which makes it count as two possibilities again, the other way around)? – Bobson Dugnutt Feb 19 '16 at 14:09
• Vanishing points do not guarantee that a cube will look like figure 1. Try looking at a real cube from different angles: depending on your point of view, you may see just two faces (fig 1) or you may see three (fig 4). Vanishing points just mimic the actual perspectives you get with such experiments. – David K Feb 19 '16 at 14:20
• Anyway the point is you changed the perspective from figure 4 to figure 5, and this changes the number of colorings of the 3-cube drawing, so perhaps it changes the number of colorings of the 4-cube drawing too. – David K Feb 19 '16 at 14:22
• @DavidK Well, if you could see through the cube (which we can here) you'd still be able to "interpret" which face is in front of the other in two different ways. I disagree that this changes the number of colorings of the 3-cube drawing if we draw the inner cube in Fig. 4 with vanishing points; the problem as it is now is that the front and the back surfaces are the same size, and therefore you cannot distinguish them; this is not the case when introducing vanishing points; then the front will be bigger in the projection. – Bobson Dugnutt Feb 19 '16 at 14:26

## 1 Answer

I think I figured it out!

Looking at a layout like the one in Fig. 5, we'll regard only one of the four sections, or "wings". Instead of counting the layers so that the central square is counted, let us count layers so that the first layer is the one just outside the central square. Then, for one layer there is only one possible configuration. For two layers there are two (two "single" faces or one "double" face). For three layers there are four, and so on. So for $l$ layers there are $2^{l-1}$ possible configurations of one wing. Disregarding any concerns of rotational symmetries, we can view the three other sides as independent of the first one. So all in all there are $2^{4(l-1)}$ configurations for all four wings.

But all this assumed that the central face could only be the central square (layer number zero, if you will), so there are more possibilities. But letting the central face cover one more layer produces the same number of possible configurations as if you removed one layer and kept the central square as the central face. But we already have a formula for this (where $l$ now is one smaller): $2^{4(l-2)}$. Such a term is added for each possible expansion of the central face, so we get:

$$2^{4(l-1)}+2^{4(l-2)}+2^{4(l-3)}+...+2^{4(1-1)}+1$$ The $+\;1$ comes from letting the entire thing be the central face (and our formula can't take $l<1$). Thus we get

$$1+\sum_{k=1}^l 2^{4(k-1)}=1+\frac{1}{15}\left( 2^{4l}-1\right)$$

I already figured out the relationship between layers and the dimension $n$, but there I counted the central face as a layer, so the new relationship is $$l=2^{n-2}-1$$ which is inserted into the newly found formula for number of possible configurations:

$$1+\frac{1}{15}\left( 2^{4\left(2^{n-2}-1\right)}-1\right)=$$ $$\color{blue}{P(n)=1+\frac{1}{15}\left(2^{2^n-4} -1\right)}$$ is the number of possible configurations of faces between four vertices in an $n$-cube!

The function explodes after the first two:

$$\begin{array}{c|lcr} n & P(n)\\ \hline 2 & 1 \\ 3 & 2 \\ 4 & 274 \\ 5 & 17895698 \\ 6 & 76861433640456466 \\ \vdots & \vdots \end{array}$$

Here's a logplot of the beast: And here we see that the number of digits in $P(n)$ is growing exponentially (with $n$ again on the first axis): 