Number of different ways to color vertices
of a n-dimensional hypercube using at most K colors

The purpose of this document is to (make a program to) find a[n], defined as the title.
Two ways of coloring are regarded as the same if they are conjugated by a permutation of the vertices caused by a rotation of the hypercube.

According to the Pólya enumeration theorem, a[n] = ∑Kcy(g) (g∈G')/#(G'),
where G' is the set of all permutation of the vertices caused by a rotation,
and cy(g) is the number of the cycles of the g, explained more precisely later.

Symbols: ∑: sum, ∏: product, R: real number. Assume n to be a positive integer.

--- Description of the rotation ---

We use ordinary n-dimensional cartesian coordinate system Rn: {(x1, x2, ..., xn); xi∈R}.
Define e[i] as the i-th basis vector, with the direction of the axis xi, and the size of 1.
Consider the 2n points described as (±1, ±1, ..., ±1) are the vertices of the hypercube.

Let g be a linear mapping from Rn to Rn, and v be a subset of Rn.
g(v) means the image of v by g, and gk(v) means the image of v by k-times g.
Define Gn as a set of linear mapping g from Rn to Rn satisfying:
(1) For each basis vector e[i], there exist k and g(e[i]) = e[k] or g(e[i]) = -e[k]
(2) If i≠j, then g(e[i])≠g(e[k]), g(e[i])≠-g(e[k]).

Let g∈Gn, so for each e[i], there exist k and g(e[i]) = e[k] or g(e[i]) = -e[k].
Define a n-number permutation σg and a n-term sequence {κg} as following:
If g(e[i]) = e[k] then κg[i] = 1, and otherwise κg[i] = -1, and for the both case, σg(i) = k.
In other words, g(e[i]) = κg[i] eg(i)].

On the contrary, any pair of σ and {κ} gives different g satisfying (1),(2) above,
if σ is n-number permutation and {κ} is n-term sequence with each term 1 or -1.

Claim 1: All permutations of the vertices of hypercube by rotation are included in Gn.

Proof: Interpret such rotations as mapping each surface to another of the hypercube. Each surface is described as the equation xi = 1 or xi = 1. Take σ(i) and {κ}[i] as the surface xi = 1 is mapped to the surface xσ(i) = κ[i]. Then, they give g∈Gn.

However, the contrary is not true; Gn also contains mirroring mappings.

Assumption: According to the theory of linear algebra, g∈Gn works as a rotation if and only if the determinant of Xg equals 1, where Xg is the n×n matrix representing g, which means Xg(v) = g(v) for any column vector v∈R^n.

Define d(g) as the determinant of Xg described above. Then we get:
   Claim 2: d(g) = sign(σg)∏κg[i], and g works as a rotation if and only if d(g) = 1.

Proof: Substituting e[i] for v into Xg(v) = g(v), it turns out that the i-th row vector of Xg equals g(e[i]). In other words, Xg[i, σg(i)] = κg[i] for 1≤i≤n, and the other entries are all 0. By the definition of the determinant of matrices, we get d(g) = sign(σg)∏κg[i].

--- Definition of cy(g) ---

We can interpret g∈Gn as a permutation of the 2n surfaces, and also as a permutation of the 2n vertices of the hypercube. They behave in different ways.

Example of n=3:
Let A:(surface x=1), B:(surface y=1), C:(surface z=1), a:(surface x=-1), b:(surface y=-1), c:(surface z=-1),
P:(1,1,1), Q:(1,1,-1), R:(1,-1,1), S:(1,-1,-1), T:(-1,1,1), U:(-1,1,-1), V:(-1,-1,1), W:(-1,-1,-1).
Let g∈G3 given by σg(1)=2, σg(2)=3, σg(3)=1, κg[1]=κg[2]=κg[3]=1.
The permutation of surfaces is as follows: g(A)=B, g(B)=C, g(C)=A, g(a)=b, g(b)=c, g(c)=a.
The permutation of vertices is: g(P)=P, g(Q)=T, g(R)=Q, g(S)=U, g(T)=R, g(U)=V, g(V)=S, g(W)=W. (Precisely, g(Q)=g(1,0,0)+g(0,1,0)+g(0,0,-1)=(0,1,0)+(0,0,1)+(-1,0,0)=(-1,1,1)=T)
Using the cycle notation, they are written as (ABC)(abc) or (P)(QTR)(SUV)(W)

Define cy(g) as the number of cycles of g as a permutation of the vertices of the hypercube (not the permutation of the surfaces). For example, if g is the one given above, cy(g) = 4 because g has 4 cycles: (P), (QTR), (SUV), and (W).

We can also define cy(g) in other words. Define ord(v,g) as the least positive integer k such that gk(v)=v. Define #(g,q) as the number of vertices of the hypercube whose position vector v satisfies ord(v,g)=q. Then the number of cycles in g with the length q equals #(g,q)/q, so their sum ∑#(g,q)/q is equivalent to cy(g).

However, it is not an efficient way to examining 2n vertices for every g.

--- Classify of g ---

Let σ be a permutation. Define S(σ, w) as the smallest set including w and closed by σ, which means if y∈S(σ, w) then σ(y)∈S(σ, w).

Let g∈Gn and w goes 1 from n giving S(σg, w). Some may give the same set. Assume that there given m different sets. Call them S[1], S[2], ..., S[m]. (In other words, they are the "cycles" of the σg.) Using them, Define Mg as the following steps:
(1) Let s[i] be the size of the set S[i] for each 1≤i≤m.
(2) Multiply s[i] by ∏κg[k] (k∈S[i])
(3) For the uniqueness, sort them in some order, for example the descending order.
Then, that is the sequence Mg.

Proposition 1:
Let g, g'∈Gn. Suppose that Mg and Mg' are the same sequences. Then, #(g, q) = #(g', q) for any q, (it means cy(g) = cy(g')), and also d(g) = d(g').

Proof: We show that there exist f∈Gn such that f(g(v)) = g'(f(v)) for any vector v∈Rn.
Let m and S[1], S[2], ..., S[m] described above. Since Mg and Mg' are the same, we can take S'[1], S'[2], ..., S'[m] which are m different set given by the form S(σg', w), such that S[i] and S'[i] have the same size and ∏κg[k] (k∈S[i]) = ∏κg'[k'] (k'∈S'[i])
   Discuss with a specific i. Let the size of S[i] be s, which is also the size of S'[i]. Take w∈S[i] and w'∈S'[i]. Assume gt(e[w]) = ce[k] and g't(e[w']) = c'e[k']. Then take σf(k) = k' and κf[k] = c'/c. By the definition of S(σ, w), When t goes from 1 to s, each t gives different k. So σf(y) and κf[y] are determined for each y∈S[i]. Similarly, each t gives different k' so σf(y) takes all value in S'[i]. Each number of {1, 2, ..., n} appears in S[i] for some i and also in S'[i'] for some i', so σf and {κf} are completely determined to give f∈Gn.
   Then, confirm f(g(v)) = g'(f(v)). Again discuss with a specific S[i] and using the description above, we have f(gt(e[w])) = g't(e[w']) for 1≤t≤s. It means f(g(gt-1(e[w]))) = g'(g't-1(e[w'])), so if we also have f(gt-1(e[w])) = g't-1(e[w']), then it follows f(g(v)) = g'(f(v)) where v=gt-1(e[w]). The only case to check is when t-1=0. Consider that while g works s times successively upon w, all κg[y] (y∈S[i]) are multiplied one by one. Then gs(e[w]) = e[w] ∏κg[k] (k∈S[i]). Similarly, g's(e[w']) = e[w'] ∏κg'[k'] (k'∈S'[i]). We already have f(gs(e[w])) = g's(e[w']) and ∏κg[k] (k∈S[i]) = ∏κg'[k'] (k'∈S'[i]). Those lead to f(e[w])=w', which was the case to check.
   Since each basis vector appears somewhere and the mapping is linear mapping, now we have f(g(v)) = g'(f(v)) for any vector v∈Rn. Substituting g(v) for v, we have f(g(g(v))) = g'(f(g(v)) = g'(g'(f(v)) Repeating similarly, we have f(gk(v)) = g'k(f(v)). It means if gk(v) = v than g'k(f(v)) = f(v) and if gk(v) ≠ v than g'k(f(v)) ≠ f(v). Then, each vertex v of the hypercube corresponds to another vertex F(v) such that org(g,v) = ord(g',f(v)). It means cy(g) = cy(g').
   d(g) = d(g') is easily confirmed by Claim 2: d(g) = sign(σg)∏κg[i] far above.

Now, we can define #(M,q) = #(g,q), Cy(M) = cy(g), D(M) = d(m) by taking g such as Mg=M.

Proposition 2:
Let M={M[1], M[2], ..., M[m]} be a m-length sequence with non-zero integer and ∑|M[i]|=n. Define H(M) as the number of g∈Gn such that Mg = M. Then, H(M) is given by:
H(M) = 2^(n-m) n! / ∏|M[k]| (1≤k≤m) / ∏(the number of i such that |Mi|=y)! (1≤y≤n).

Proof: There are 2m patterns to give signs to every M[i], and there are 2n patterns to give signs to κg[i]. 2n patterns are equally divided into 2m patterns. So 2n-m is the number of patterns of κg satisfying Mg=M. So the number of patterns of σg is the rest part. The way to divide n numbers into M[1], M[2], ..., M[k] subgroups is n!/∏|M[k]|! (1≤k≤m). And consider that each subgroups makes (|M[k]|-1)! circular permutation. Finally, remove distinctions between subgroups with the same size. These are realized by the expression of H(M) above.

Claim 3: a[n] = ∑H(M)KCy(M)/∑H(M), where M takes all sequence by non-zero integer, satisfying ∑|M[i]| = n and D(M) = 1.

Proof: According to the Pólya enumeration theorem, a[n] = ∑Kcy(g) (g∈G')/#(G'), where G' is the set of all permutation of the vertices caused by a rotation. By Claim 1 and 2, G' = {g∈Gn and d(g) = 1}. Using Proposition 1 and 2, we can gather g with the same Mg which result the claim above.

--- Calculation for Cy(M) ---

Proposition 3:
Suppose M = [n]. If q|n then #(M,q) = ∑μ(q/d)×2d (d|q), otherwise #(M,q) = 0.
Also, if n is odd then D(M) = 1 and otherwise D(M) = -1.
Here μ(x) is the Möbius function and x|y means y is divisible by x.

Proof: Take g with σg(i) = i+1 (i≠n), σg(n) = 1, and κg[i] = 1 for each i, then Mg = M.
   Let v be a position vector of a vertex of the hypercube, expressed as v = ∑a[w]e[w] (1≤w≤n), where a[w] is 1 or -1 for each w. Considering g(v) = ∑a[w]eg(w)] (1≤w≤n) and the feature of σg, we get gk(v) = ∑a[w]e[w+k] (1≤w≤n) (if w+k>n, e[w+k] means e[w+k-n]).
   Regardless of a[w] we have gn(v) = v. It means ord(v,g)|n, and the last part of the proposition follows from here.
   Then let q be a divisor of n. gq(v) = v means a[w] = a[w+q] for each w (if w+q>n, a[w+q] means a[w+k-n]). To satisfy this, we can set arbitrary a[1],a[2], ..., a[q], but a[w] (w>q) are determined automatically. There are 2q kinds of such combination of {a[i]}, so there are 2q vertices satisfying gq(v) = v. So, ∑#(g,d) (d|q) = 2q. In programming this form is rather useful, but by the Möbius transform, we have #(g,q) = ∑μ(q/d)×2d (d|q).
   d(g) is easily confirmed by Claim 2.

Proposition 4:
Suppose M = [-n]. If q is odd then #(M,q) = 0.
If n is odd, D(M) = 1 and let M' = {n}, then #(M,2q) = #(M',q).
If n is even, D(M) = -1 and let M' = {-n/2,-n/2}, then #(M,2q) = #(M',q).

Proof: Take g with σg(i) = i+1, κi = 1 (i≠n), and σg(n) = 1,κg[n] = -1, then Mg = M.
   Let v = ∑a[w]e[w] similarly as the proof above. Regardless of a[w] we have gn(v) = -v (≠v) this time. Since g2n(v) = v, ord(g,v) is a divisor of 2n but is not a divisor of n. That means that ord(g,v) is even.
   Let g'∈G satisfy g'(v) = g(g(v)) for any v. Then, ord(g,v) = 2q means ord(g',v) = q. If n is odd, σg' is also one cycle permutation (consider the equation 2x≡0 (mod n)), and ∏κg'[i] = 1 (because there appear two negative terms in {κg'}). Thus Mg' = {n}. If n is even, σg' divides into two cycles and each cycle has one negative κg'[i]. Thus, Mg' = {-n/2,-n/2}.
   d(g) is easily confirmed by Claim 2.

Proposition 5:
Suppose M has more than one term. Let M', M" be its two subsequences and those fusion equals M. Then #(M,q) = ∑#(M',x)#(M",y) (LCM(x,y) = q), where LCM(x,y) is the least common multiple of x, y. Also D(M) = D(M')D(M").

Proof: Take g, g', and g" such as Mg = M, Mg' = M', and Mg" = M". σg has several cycles. Some correspond with M' and the other correspond with M". Let S', S" be subsets of {1, 2, ..., n} such that: For each 1≤w≤n, if the cycle S(σg, w) correspond with M' then w∈S', and otherwise w∈S".
   Let v' = ∑a[w]e[w] (w∈S'), v" = ∑a[w]e[w] (w∈S"), where a[w] is 1 or -1 for each w. Then, g(v') is also a linear combination of e[w] (w∈S') and g(v") is a linear combination of e[w] (w∈S").
   Suppose gk(v'+v") = v'+v". Since there are no common terms between S' and S", it requires both gk(v') = v' and gk(v") = v". Therefore, ord(v'+v",g) = LCM(ord(v',g),ord(v",g)). Here, the number of patterns of a[w] satisfying ord(v',g) = x, is equivalent to #(g',x) because v' is restricted into a subspace, whose dimension equas the size of S', which equals the dimension of g'. #(g",y) is similar. #(g',x)= X means there are X patterns of a[w] (w∈S') and #(g",y) = Y means Y patterns of a[w] (w∈S"). Then, there are XY patterns of a[w] satisfying both. D(M) = D(M')D(M") is obtained by sign(σ')sign(σ") = sign(σ'σ") and else.

--- Algorithm and some results ---

I sorted the sequence M[i] by the descending order with the absolute value, and if absolute value the same, positive integers higher priority.

Let i start from 1.
   Assume that: About M such as ∑|M[i]| < i are already calculated.
   Calculate #(M,q),D(M) for M = [n] using Proposition 3.
   For each 1≤j<i, and for each M'=[±j],
      For each M" such that ∑|M"[i]|=n-j and M'[1] has higher priority than M"[1],
      (Every fused M is obtained only once under this restriction)
         Calculate #(M,q),D(M) for M =(fusion of M', M"), using Proposition 5.
   Calculate #(g,q),D(M) for M = [-n] using Proposition 4.
Next i (until somewhere).
Let i start from 1 again.
   For each M satisfying ∑|M[i]|=i,
      if D(M) = 1, calculate H(M) by Proposition 2 and Cy(M)=∑#(g,q)/q
   Then, output.

Here is my source code written by C language: hypercube.c
And the output for 1≤n≤10: hypercube_output.txt
And the result with K=2 calcurated by Maxima: hypercube_an.txt

Generally, integer overflow, run time, and memory may limit programs. This time, the integer overflow was the limitation. I attemped to check integer overflow using such function:

   int safe(int x,int y){ //safe means x*y will not overflow assuming x,y>0
      int i; while(x){x/=2;i++;} while(y){y/=2;i++;}
      if(i>31){printf("Alert from safe(x,y)\n");return 0;}
   return 1;}

Then I had one alert when n=10. So, a[10] might be wrong.


I would like to thank mleparadonan for providing this interesting topic in yahoo questionnaire. I made much reference to several Wikipedia pages referring to rotation matrix, the Pólya enumeration theorem, and etc. And I looked up the Weblio online English dictionary many times. Of course this work also owes to developers of the Borland (compiler) and the Maxima (mathematical software), and etc.

2014/2/13 Azuma Seiichi

inserted by FC2 system