Painting hyper-cubes

The hardest part of this problem is to realize that in order to make the permutations unique you need to think in terms of $n$ pairs of colors as opposed to $2n$ sides . The reason for this is that under rotation all you really do is swap axes. Apart from breaking symmetry (making a mirror image) you can reach every permutation of the axes and their pairs of opposing, coloured sides.

Therefore, the correct approach is as follows:

1) Find the number of symmetrical pairs; that is - pairs whose mirror image is the same - aka, have the same color on each side.

This number (sp) is equal to $k$ : one pair for each color.

2) Find the number of a-symmetrical pairs; that is - pairs whose mirror image is not the same - aka, have different colors on each side.

This number (ap) is equal to $k (k - 1) / 2$ . Note that we divide by two because the pair red-green is the same as green-red: the sides of a pair are not ordered.

3) Find the number of distinct multisets of $n$ pairs (one for each axis!). This is equivalent to number of combinations with repetition . It is with repetition because multiple axes can have the same pair of colors of course; the pairs need not be distinct. The formula for this "number of combinations of x choose y with repetition" is ${x+y-1 \choose y}$ .

This number (np) is therefore equal to ${sp + ap + n - 1 \choose n}$ . Namely, we have in total $sp + ap$ distinct pairs and need to choose $n$ , one for each axis, with repetition ("putting back").

4) Find the number of distinct sets of $n$ pairs that are a-symmetric; whose mirror image is different. That means that each pair must be a-symmetric, but also that each element in the set of pairs must be distinct. So now we need to choose $n$ from the a-symmetrical pairs without repetition. The formula for this "x choose y" or number of y-combinations is ${x \choose y}$ .

This number (nap) is therefore ${ap \choose n}$ .

5) Find the number of distinct sets of $n$ pairs that are symmetric. This is of course the total number of pairs minus the a-symmetric ones:

This number (nsp) is $np - nap$ .

6) Finally we can calculate the number of permutations of the hyper-cube itself.

${f(n, k) = nsp + 2 \times nap}$

The reason that the a-symmetrical sets of pairs are counted twice is because their mirror image is different, so they will cause two different hyper-cubes that can not be made equal under rotation.

Note that ${x \choose y}$ is short for $x! / y!(x-y)!$ .

So, this requires to calculate the factorial of numbers as large as ap. For n=67 that is 2211, which doesn't fit in a normal builtin integer. You can use a big int library, or you can make use of the fact that you only need to know the answer modulo 10000. In that case you can keep all numbers small, also during the calculations. For that to work however you need a more optimized algorithm to calculate the binomial ${x \choose y}$ modulo 10000.

Without calculating modulo 10000 you can verify that the number of permutations for n=67 and k=23 is 1614652659246460685133480072022754982197377870904804029782415092786252018 using a bigint library. But that doesn't prove that there isn't some value of k for a smaller value of n. However, since it was given that k < 200 it is doable to calculate all permutations exactly this way for an increasing n for every k up till 200.

The program that I wrote, in C++, to check everything needs to do the calculations modulo 10000. I couldn't figure out how to calculate the binomial without using a bigint library however.

Here is my program:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

#include <iostream>
#include <algorithm>
#include <cstdint>
#include <cassert>
#include <boost/multiprecision/cpp_int.hpp>

using bigint_t = boost::multiprecision::cpp_int;

// Computer Science.
// Discrete Mathematics.
// Combinatorics.

// Given a set of n distinct objects, return the number of
// possible sets we can get when choosing m objects without
// replacement (so the elements of the resulting set will
// also be distinct).
uint64_t binomial(uint64_t n, unsigned int m)
{
  assert(m <= n);

  // We do all calculations modulo 10000.
  n %= 10000;
  if (m > n)
    n += 10000;

  bigint_t result = 1;

  for (unsigned int i = 1; i <= m; ++i, --n)
    result = result * n / i;

  result %= 10000;
  return static_cast<uint64_t>(result);
}

int main()
{
  // Number of dimensions.
  for (unsigned int n = 2; n < 10000; ++n)
  {
    // Number of colors.
    for (unsigned int k = 2; k < 10000; ++k)
    {
      // The number of symmetric color pairs (of opposite faces) is.
      unsigned int sp = k;                 // Both sides have the same color.
      // The number of a-symmetric color pairs (of opposite faces) is.
      uint64_t ap = k * (k - 1) / 2;       // The two sides have a different color.
      // The number of distinct sets of n pairs.
      uint64_t np = binomial(sp + ap + n - 1, n);
      // The number of distinct sets of n pairs that are a-symmetric;
      // this means that each pair must be a-symmetric, but also that
      // each element in the set of pairs must be distinct.
      uint64_t nap = (ap < n) ? 0 : binomial(ap, n);
      // The number of distinct sets of n pairs that are symmetric.
      uint64_t nsp = np - nap;
      // The number of distinct n-dimensional (hyper)cubes painted
      // out of a palet of k colors.
      uint64_t nhc = nsp + 2 * nap; // A-symmetric sets of pairs count
                                    // double: also their mirror image.

      nhc %= 10000;
      if (nhc == 2018)
      {
        std::cout << "n = " << n << "; k = " << k << "; number of permutations modulo 10000 = " << nhc << std::endl;
      }
    }
  }
}

Which prints

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

n = 9; k = 9558; number of permutations modulo 10000 = 2018                                                                                                                                  
n = 11; k = 471; number of permutations modulo 10000 = 2018                                                                                                                                  
n = 13; k = 3271; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 13; k = 9521; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 35; k = 451; number of permutations modulo 10000 = 2018                                                                                                                                  
n = 36; k = 1923; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 36; k = 7152; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 37; k = 6201; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 41; k = 8777; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 43; k = 4721; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 50; k = 388; number of permutations modulo 10000 = 2018                                                                                                                                  
n = 50; k = 1913; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 53; k = 8731; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 65; k = 476; number of permutations modulo 10000 = 2018                                                                                                                                  
n = 65; k = 2476; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 66; k = 4264; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 66; k = 5802; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 67; k = 23; number of permutations modulo 10000 = 2018                                                                                                                                   
n = 71; k = 3027; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 75; k = 2289; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 80; k = 8845; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 81; k = 6947; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 82; k = 6778; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 96; k = 6777; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 105; k = 4914; number of permutations modulo 10000 = 2018                                                                                                                                
n = 129; k = 6636; number of permutations modulo 10000 = 2018                                                                                                                                
n = 130; k = 6278; number of permutations modulo 10000 = 2018                                                                                                                                
n = 133; k = 321; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 133; k = 4753; number of permutations modulo 10000 = 2018                                                                                                                                
n = 136; k = 7127; number of permutations modulo 10000 = 2018                                                                                                                                
n = 137; k = 6167; number of permutations modulo 10000 = 2018                                                                                                                                
n = 138; k = 6946; number of permutations modulo 10000 = 2018                                                                                                                                
n = 140; k = 7531; number of permutations modulo 10000 = 2018                                                                                                                                
n = 140; k = 8022; number of permutations modulo 10000 = 2018                                                                                                                                
n = 146; k = 9117; number of permutations modulo 10000 = 2018                                                                                                                                
n = 147; k = 4082; number of permutations modulo 10000 = 2018                                                                                                                                
n = 147; k = 6022; number of permutations modulo 10000 = 2018                                                                                                                                
n = 150; k = 8475; number of permutations modulo 10000 = 2018                                                                                                                                
n = 160; k = 470; number of permutations modulo 10000 = 2018                                                                                                                                 
n = 160; k = 4231; number of permutations modulo 10000 = 2018                                                                                                                                
n = 180; k = 6741; number of permutations modulo 10000 = 2018                                                                                                                                
n = 180; k = 9670; number of permutations modulo 10000 = 2018                                                                                                                                
n = 200; k = 9732; number of permutations modulo 10000 = 2018                                                                                                                                
n = 201; k = 3819; number of permutations modulo 10000 = 2018                                                                                                                                
n = 204; k = 88; number of permutations modulo 10000 = 2018                                                                                                                                  
n = 210; k = 1001; number of permutations modulo 10000 = 2018                                                                                                                                
n = 212; k = 2123; number of permutations modulo 10000 = 2018                                                                                                                                
n = 215; k = 22; number of permutations modulo 10000 = 2018                                                                                                                                  
n = 235; k = 5446; number of permutations modulo 10000 = 2018                                                                                                                                
n = 237; k = 6498; number of permutations modulo 10000 = 2018
...