正四面体の頂点をN色で塗るパターン

問題

　N色のペンを使って、正四面体の頂点を塗ろうとしています。塗り方のパターンは何通りあるでしょうか？ただし、回転して同じものは同一と考えます。

アプローチ

　対称性のあるものを塗るので、ポリアの数え上げを使います。対称性には主に２つがあります。

1. rotation
2. reflection

　今回は、rotation（回転）のみを考えます。ちなみに、reflection(反射)はある反射軸（反射面）を考えたときにちょうど鏡で反射したような形になっている対称性のことを指します。
　正四面体に対する回転操作全体を群で表し、それぞれの要素において不変なカラーリングパターンの平均値を求めてあげれば、欲しい値がえられます。ある写像において不変なカラーリングの集合は、その写像の軌道の数に等しいです。（この辺りの証明とかより詳細な背景は組み合わせ数学の本に載ってます。）
　あとは、群の要素をどうやってもってくるか。。頂点の数は4つなので、すべての対称群を列挙したとしても4!=24個でそこから回転操作になっているものだけをがんばって抽出してもいいです。しかしWikipedia情報によると、正四面体の回転操作を表す群はalternating subgroupと同一らしいので、偶順列のみをとってくればOKということになります。

ソースコード

　N=1のとき1、N=2のとき5、N=3のときは15らしいです。

view plainprint?

1. bool isEvenPermutation(vector<int> v) {  
2.     int exchange = 0;  
3.     for (int i = 0; i < (int)v.size(); i++) {  
4.         if (v[i] == i)  
5.             continue;  
6.         ++exchange;  
7.         for (int j = i+1; j < (int)v.size(); j++) {  
8.             if (v[j] == i) {  
9.                 swap(v[i], v[j]);  
10.                 break;  
11.             }  
12.         }  
13.     }  
14.     return exchange % 2 == 0;  
15. }  
16.   
17. int orbitCount(vector<int> v) {  
18.     int cnt = 0;  
19.   
20.     for (int i = 0; i < (int)v.size(); i++) {  
21.         if (v[i] == -1)  
22.             continue;  
23.         ++cnt;  
24.         int j = i;  
25.         while (v[j] != -1) {  
26.             int tmp = v[j];  
27.             v[j] = -1;  
28.             j = tmp;  
29.         }  
30.     }  
31.     return cnt;  
32. }  
33.   
34. long long power(long long x, long long y) {  
35.     long long ret = 1;  
36.     for (int i = 0; i < y; i++)  
37.         ret *= x;  
38.     return ret;  
39. }  
40.   
41. int main() {  
42.     long long color;  
43.     cin >> color;  
44.   
45.     vector<int> v;  
46.     for (int i = 0; i < 4; i++)  
47.         v.push_back(i);  
48.   
49.     int g = 0;  
50.     long long pattern = 0;  
51.     do {  
52.         if (isEvenPermutation(v)) {  
53.             ++g;  
54.             pattern += power(color, orbitCount(v));  
55.         }  
56.     } while (next_permutation(v.begin(), v.end()));  
57.   
58.     assert(g > 0);  
59.     assert(pattern % g == 0);  
60.   
61.     cout << "Pattern: " << pattern/g << endl;  
62. }  

bool isEvenPermutation(vector<int> v) {
    int exchange = 0;
    for (int i = 0; i < (int)v.size(); i++) {
        if (v[i] == i)
            continue;
        ++exchange;
        for (int j = i+1; j < (int)v.size(); j++) {
            if (v[j] == i) {
                swap(v[i], v[j]);
                break;
            }
        }
    }
    return exchange % 2 == 0;
}

int orbitCount(vector<int> v) {
    int cnt = 0;

    for (int i = 0; i < (int)v.size(); i++) {
        if (v[i] == -1)
            continue;
        ++cnt;
        int j = i;
        while (v[j] != -1) {
            int tmp = v[j];
            v[j] = -1;
            j = tmp;
        }
    }
    return cnt;
}

long long power(long long x, long long y) {
    long long ret = 1;
    for (int i = 0; i < y; i++)
        ret *= x;
    return ret;
}

int main() {
    long long color;
    cin >> color;

    vector<int> v;
    for (int i = 0; i < 4; i++)
        v.push_back(i);

    int g = 0;
    long long pattern = 0;
    do {
        if (isEvenPermutation(v)) {
            ++g;
            pattern += power(color, orbitCount(v));
        }
    } while (next_permutation(v.begin(), v.end()));

    assert(g > 0);
    assert(pattern % g == 0);

    cout << "Pattern: " << pattern/g << endl;
}