Cコードのフォームの数は

数え上げの問題を考えてみました。

問題

十分に長く、十分に細い６本の指を持つ宇宙人が24fギターを弾いています。Cコードの異なるフォームの数を求めなさい。
ただし、Cコードとはドミソの３音からなる和音です。これら意外の音を鳴らしてはいけませんし、これらの３音はすべて鳴っていないといけません。
それぞれの弦は解放弦でもいいし、ミュートしてもいいこととします。

全探索解

24フレット（＝２音階分）あるのである音をならすポジションは2個（解放弦が目的の音に等しいときは3個）あります。よってそれぞれの弦について、ドミソのいずれかの音を鳴らすことのできるポジションは高々3 * 3 = 9個です。これにミュートする場合を加えると、一つの弦の有効な押え方は10個程度です。全体で10^6通りを考えればよいため、全探索でも十分計算できます。
また、音階を12を法とした正数群と捉えるとプログラミングしやすいです。

答えは110362とおりです。僕が使っているフォームは5個くらいなので、聞いたことのない響きがたくさん存在するということになります。

#include <iostream>

using namespace std;

int open[] = {4, 9, 2, 7, 11, 4};

long long ret;

void solve(int p, int mask) {
    if (p == 6) {
        if (mask+1 == (1<<3))
            ++ret;
        return;
    }

    // mute this string
    solve(p+1, mask);

    for (int i = 0; i <= 24; i++) {
        int q = (open[p] + i) % 12;
        if (q == 0)
            solve(p+1, mask|1<<0);
        else if (q == 4)
            solve(p+1, mask|1<<1);
        else if (q == 7)
            solve(p+1, mask|1<<2);
    }
}

int main() {
    solve(0, 0);
    cout << ret << endl;
    return 0;
}

包除原理を使った解

ド、ミ、ソをA, B, Cと表すことにします。また、ミュートはDで表すことにします。S(x,y, ..)を{x, y, ...}内の要素のみを用いたときに6弦を弾くパターンの数とします。

 包除原理により求めたい数は、
 S(A, B, C, D)
- S(B, C, D) - S(A, C, D) - S(A, B, D) - S(A, B, C)
+ S(A, B) + S(A, C) + S(A, D) + S(B, C) + S(B, D) + S(C, D)
-S(A) - S(B) - S(C) - S(D)　　（式１）
となります。と思っていましたが、実は違います。

上の値で求めたのは、少なくとも一つの弦がミュートされていて、かつ、コードCがなっているフォームの数です。ミュートしないフォームについては数えられていません。

ミュートしないフォームのパターン数は、
S(A, B, C) - S(A, B) - S(A, C) - S(B, C) + S(A) + S(B) + S(C)　　（式２）
です。

（式１）+ （式２）より求めたい数は、
 S(A, B, C, D)
- S(B, C, D) - S(A, C, D) - S(A, B, D)
+ S(A, D) + S(B, D) + S(C, D)
- S(D) 　　（式３）

となります。がんばれば手で計算できそうですが、プログラミングで解きました。（式３）から{A, B, C}の冪集合は打ち消しあって答えに影響しないので、Dを含まない要素はスキップしています。

#include <iostream>

using namespace std;

int cnt[][4] = {    // cnt[i] is (# of C, # of E, # of G, # of mute) in the i-th string
    {2, 3, 2, 1},
    {2, 2, 2, 1},
    {2, 2, 2, 1},
    {2, 2, 3, 1},
    {2, 2, 2, 1},
    {2, 3, 2, 1}
};

int main() {
    long long ret = 0;

    for (int k = 0; k < 1<<4; k++) {
        if (!(k & 1 << 3)) continue;     // cancelled term
        long long ptr = 1;
        for (int i = 0; i < 6; i++) {
            int sum = 0;
            for (int j = 0; j < 4; j++) {
                if (k & 1 << j)
                    sum += cnt[i][j];
            }
            ptr *= sum;
        }

        if (__builtin_popcount(k) % 2)
            ret -= ptr;
        else
            ret += ptr;
    }

    cout << ret << endl;
    return 0;
}