Q39 隣り合うと消えちゃうんです

C#のソース

using System;

class Program
{
    static void Main()
    {
        for (decimal N = 3; N <= 11; N++) {
            Console.WriteLine("N={0}での解は{1}", N, Solve(N));
        }
    }

    // 包除原理で解く
    static decimal Solve(decimal pN)
    {
        // 全事象
        decimal PatternCnt = DeriveKaijyou(pN * 2);
        for (decimal I = 1; I <= pN; I++) {
            PatternCnt /= 2;
        }

        decimal WasyuugouCnt = 0;

        // n(A∪B∪C∪ ・・・ ) の値を求める
        for (int I = 1; I <= pN; I++) {
            // 符号
            int SignVal = (I % 2 == 0 ? -1 : 1);

            // nCi を求める
            decimal CombiCnt = DeriveCombi(pN, I);

            // 各場合の数を計算
            decimal wkCnt = DeriveKaijyou(pN * 2 - I);
            for (decimal J = 1; J <= pN - I; J++) {
                wkCnt /= 2;
            }

            WasyuugouCnt += SignVal * CombiCnt * wkCnt;
        }

        PatternCnt -= WasyuugouCnt;
        PatternCnt /= DeriveKaijyou(pN);
        return PatternCnt;
    }

    // nCrを求める
    static decimal DeriveCombi(decimal pN, decimal pR)
    {
        decimal WillReturn = 1;
        for (decimal I = pN; pN - pR + 1 <= I; I--) {
            WillReturn *= I;
        }
        for (decimal I = 2; I <= pR; I++) {
            WillReturn /= I;
        }
        return WillReturn;
    }

    // 階乗を求める
    static decimal DeriveKaijyou(decimal pTarget)
    {
        decimal WillReturn = 1;
        for (decimal I = 2; I <= pTarget; I++) {
            WillReturn *= I;
        }
        return WillReturn;
    }
}

実行結果

N=3での解は5
N=4での解は36
N=5での解は329
N=6での解は3655
N=7での解は47844
N=8での解は721315
N=9での解は12310199
N=10での解は234615096
N=11での解は4939227215

解説

緑、青、黄の3色で考察します。

緑が隣接する配置の集合をA
青が隣接する配置の集合をB
黄が隣接する配置の集合をC
とおくと

N(A∪B∪C) = N(A)+N(B)+N(C)-N(A∩B)-N(A∩C)-N(B∩C)+N(A∩B∩C)
=  3*5!/(2!*2!)
  - 3*4!/2!
  + 3!
= 60
となります。

全事象は、同じものを含む順列の公式より
6!/(2!*2!*2!) = 90

余事象を考えると
90 - 60 = 30

色を区別しないので
30/3!=5

和集合の要素数は、包除原理を使って求めることができます。