【Java】パスカルの三角形を使って組合せを求める

　前回、漸化式を使っての組合せの数を求めたが、別の解法として「パスカルの三角形」を利用して組合せを求める方法もある。パスカルの三角形とは「二項係数」とか「二項定理」とも呼ばれ、高校数学でやった二項式を展開するときの係数に合致しているが、他にも色々利用できる性質がある。

　まずは簡単に作り方を覚えてしまおう。非常に単純なので一度聞いたら忘れることもないだろう。作り方は以下のようになる。

１．頂点（一番上）に「１」を書き、ここをスタート地点とする。

２．スタート地点から左右（矢印の方向：斜め下）に向かって進んでいく。その際、交差する地点はその１つ前の値を合計する。これを繰り返す。

　これは道に例えると「網の目のように必ず２つの分岐点がある道を進むとき、その地点に最短で辿り着く方法は何通りあるか？」という数になる。つまり、地点Aに辿り着く方法が２通り、地点Bに辿り着く方法が１通りあるとき、その地点AとBが合流する地点Cは 2+1=3 通りあるという単純なものである。

　そしてこの値は、以下のように組合せを求める式の答えとも合致している。

　つまりこのパスカルの三角形を作ることをシミュレーションすれば、組合せの数も簡単に求めることができるというわけだ。さっそく上記の作り方をそのままコーディングしてみよう。

●パスカルの三角形を作る [O(hw)]

/**<h1>パスカルの三角形を作る</h1>
 * <p>パスカルの三角形を斜めに傾けた配列を作成。左上が(0,0)で右下に拡がる感じになる。</p>
 * @param w ： 横数 (1～33)
 * @param h ： 縦数 (1～33)
 * @return<b>long[][]</b> ： パスカルの三角形を配列化したもの
 */
public static final long[][] pascalsTriangle(final int w, final int h) {
    final long[][] arr = new long[h + 1][w + 1];
    arr[0][0] = 1;

    for (int i = 0; i <= h; i++) {
        for (int j = 0; j <= w; j++) {
            if (j > 0) {
                arr[i][j] += arr[i][j - 1];
            }
            if (i > 0) {
                arr[i][j] += arr[i - 1][j];
            }
        }
    }

    return arr;
}


//メインでは...
int w = 5;
int h = 4;
long[][] pascal = pascalsTriangle(w, h);    //パスカルの三角形

　パスカルの三角形を下の図のように斜め45度傾けて配列に入れたと考えれば簡単だろう。

　つまり組合せの数を求めたいなら、この表を作って、値を取得すれば良いということになる。例えば、5C3 を求めたければ、配列の pascal[3][2] = 10 が「5個のものから3個取り出す組合せ」の数になる。nCr に置き換えれば、pascal[n - r][r] となる。また表を見てわかるように、対角線で値が対称になっているので、5C3 = 5C2 (nCr = nCn-r) となり、配列の縦横を入れ替えても同じとなる。もし、関数として作って置きたいなら、以下のような感じにすれば良い。

●パスカルの三角形から組合せの数を求める [O(n²)]

/**<h1>n 個のものから r 個取り出した組合せの数を求める</h1>
 * <p>nCr をパスカルの三角形から求める。
 * <br>n, r が 大きすぎるとオーバーフローするので注意。</p>
 * @param n ： すべての数 (1～66) (負の値はエラー)
 * @param r ： 取り出す数 (1～33) (負の値はエラー)
 * @return<b>long</b> ： 組合せの数
 */
public static final long combination(final int n, final int r) {
    if (n < 0 || r < 0 || n < r) {
        throw new ArithmeticException("n = " + n + ", r = " + r);
    }
    if (r == 0 || r == n) {
        return 1;
    }
    if (r == 1) {
        return n;
    }

    //パスカルの三角形
    final long[][] pascal = pascalsTriangle(r, n - r);
    return pascal[n - r][r];
}

　漸化式での組合せ[O(n)]と比べたメリットは、計算が単純な加算しかしていないため、オーバフローが少しばかりしにくい所だろうか。また、大量に計算するなら、１つパスカルの三角形を作っておいて[O(n²)]、配列から値を取り出すだけにすれば[O(1)]、実行負荷はほとんど無くなる（例えば、30個の組合せを1000回計算するなら、漸化式では 30[O(n)]x1000回 = 30000回演算、パスカルの三角形なら 30x30[O(n²)]=900 +1000[O(1)]回 = 1900回演算で、計算量が少なくなるので速い）。しかし単体で計算するなら、毎回配列を作る[O(n²)]ので、実行速度は遅くなるので注意しよう。


　ここで試しに練習問題をやってみよう。これはどちらかというとプログラミング問題というより数学の問題だ。

４人でじゃんけんを１回するとき、あいこになる確率はどれくらいか？

//パスカルの三角形での解法
int n = 4;    //4人
long[][] pascal = pascalsTriangle(n, n); //大きさは適当(n x n あればカバーできる)
long sum = 0;    //勝敗がつく事象の合計
for (int i = 1; i < n; i++) {    //4C1～4C3 まで(4人のうち1～3人勝つ[=勝敗がつく]組合せ)
    sum += pascal[n - i][i];
}
sum *= 3;    //グー、チョキ、パーの３手でそれぞれ勝てるため、３倍する
double d = 1.0 - sum / Math.pow(3, n);    //あいこ = 全事象 - 勝敗がつく事象 [=余事象]
System.out.println(d);    //0.4814814814814815 (13/27)

　答えは 約48% (= 13/27) である。「勝ち・負け・あいこの３つだから、1/3 じゃないの？」と思った人は気をつけよう。それは前回の「コイン４枚のうち２枚が表の確率」同様、ただ単に思い込みをしているだけだ。

　簡単に解法を書いてみると、じゃんけんの手はグー・チョキ・パーの３手だから、すべての事象は 3 x 3 x 3 x 3 = 81 通りである。このうち勝敗がつくのは４人のうち１～３人の誰かが勝てばいいわけだから、4C1 + 4C2 + 4C3 の合計になり、それぞれ３手あるので３倍になる。「あいこ」になる確率は「勝敗がつかない」確率だから、余事象を用いて (1 - 勝敗がつく事象) で、1 - 14/27 = 13/27 ≒ 0.48 (48%) となる。

　ちなみに、この問題はわざわざパスカルの三角形を使った解法で試してみたが、「n人でじゃんけんを１回するとき、あいこになる確率」を一般化すると、

となるので、一発計算で求めることもできる。

//あいこになる確率を一般化したものでの解法
int n = 4;    //4人
double d = 1.0 - (Math.pow(2, n) - 2.0) / Math.pow(3, n - 1);    //あいこ = 全事象 - 勝敗がつく事象 [=余事象]
System.out.println(d);    //0.4814814814814815 (13/27)

　試しに 2人～20人でじゃんけんをしたとき、あいこになる確率を計算してみよう。

2人でじゃんけんを１回するとき、あいこになる確率 = 0.33333333333333337
3人でじゃんけんを１回するとき、あいこになる確率 = 0.33333333333333337
4人でじゃんけんを１回するとき、あいこになる確率 = 0.4814814814814815
5人でじゃんけんを１回するとき、あいこになる確率 = 0.6296296296296297
6人でじゃんけんを１回するとき、あいこになる確率 = 0.7448559670781894
7人でじゃんけんを１回するとき、あいこになる確率 = 0.8271604938271605
8人でじゃんけんを１回するとき、あいこになる確率 = 0.8838591678097851
9人でじゃんけんを１回するとき、あいこになる確率 = 0.922267946959305
10人でじゃんけんを１回するとき、あいこになる確率 = 0.9480770207793527
11人でじゃんけんを１回するとき、あいこになる確率 = 0.9653508103439516
12人でじゃんけんを１回するとき、あいこになる確率 = 0.9768892501707621
13人でじゃんけんを１回するとき、あいこになる確率 = 0.9845890700943284
14人でじゃんけんを１回するとき、あいこになる確率 = 0.9897247922786035
15人でじゃんけんを１回するとき、あいこになる確率 = 0.9931494433687528
16人でじゃんけんを１回するとき、あいこになる確率 = 0.9954328228623964
17人でじゃんけんを１回するとき、あいこになる確率 = 0.9969551687804513
18人でじゃんけんを１回するとき、あいこになる確率 = 0.9979700970332521
19人でじゃんけんを１回するとき、あいこになる確率 = 0.9986467261931519
20人でじゃんけんを１回するとき、あいこになる確率 = 0.9990978157413181

　つまり人数が増えていくたびに、あいこになる確率は限りなく 100% に近づいていく。5人以上のとき 60% を超え、9人以上のときは 90% を超えるので、もはや勝負がつかなくなる。人数が増えたとき、あいこが延々と続くようになるのはこういうことだ(笑)。人数が多いとき、4人以下で分割してじゃんけんした方が効率が良いことも理にかなっている。


　また、パスカルの三角形の作り方のコードを見て、アルゴリズマーな人なら(笑)、「あれ？このコード見たことあるな…」と思ったかもしれない。実はこれは「格子状の道の経路数を求める」(ヒョウ本 P.176～177)に載っている「動的計画法」のコードと同じだったりする。　

　その問題を挙げてみると、

以下のような格子状の道があるとき、S から G まで最短で移動する方法は何通りあるか？

というような問いである。

　実はこれも高校数学の教科書に載っているのだが、解法を簡単に書いてみると、下へ進む道を a 、右に進む道を b として１列に並べると、aaaabbbbb のようになり「9本の道から4本の道を選ぶ組合せの数」になることがわかる（9本の道から4本の道を a とすれば、残りの5本の道は b と決まるため）。そして、この格子状の経路は先のパスカルの三角形を斜めに倒した表と一致するので、全く同じコードになるわけだ。

　つまり、この格子状の経路を数え上げる問題は組合せの問題と本質的に同じになる。だから漸化式での方法でも一発で求めることができることになる。

　しかし、例えばこの格子状の道に通行止めがあった場合を考えよう。そうなると単純な組合せの計算一発では求められなくなる。その場合は、パスカルの三角形の作り方を改造すれば意外と簡単に求められるのだ。例えば先のパスカルの三角形を作るコードに通行止めのフラグでも入れて「その地点には行けない(経路数 = 0)」を挿入してしまえば良い。

●パスカルの三角形を改造して経路数を求める

//パスカルの三角形に通行止めフラグ(closed[][])を入れた
public static final long[][] pascalsTriangle(final int w, final int h, final boolean[][] closed) {
    final long[][] arr = new long[h + 1][w + 1];
    arr[0][0] = 1;

    for (int i = 0; i <= h; i++) {
        for (int j = 0; j <= w; j++) {
            if (closed[i][j]) {
                continue;
            }
            if (j > 0) {
                arr[i][j] += arr[i][j - 1];
            }
            if (i > 0) {
                arr[i][j] += arr[i - 1][j];
            }
        }
    }

    return arr;
}


//メインでは・・・
int w = 5;
int h = 4;
boolean[][] closed = new boolean[h + 1][w + 1];
closed[1][3] = true;    //通行止め
closed[2][1] = true;    //通行止め
closed[3][2] = true;    //通行止め
long[][] pascal = pascalsTriangle(w, h, closed);
System.out.println(pascal[h][w]);    //25 となる

　この手の経路数数え上げの問題は再帰を使うのも常套だが、平面を再帰で探索すると、O(2^hw) くらいの計算量はかかってしまうので、非常に重くなる。あと、マスが 100 x 100 = 10000 を超えると Stack Overflow を起こすこともあるので気をつけよう。このパスカルの三角形を改造した解法（動的計画法）なら、計算量は O(hw) でしかない。

　組合せの数と経路数の数え上げのロジックが繋がっていることを覚えておくと、利用価値があるかもしれない。色々考察してみると良いだろう。


（関連記事）
【Java】組合せの数を求める
【Java】順列の数を求める
【Java】プリミティブ型での階乗計算
【Java】1000000!のような巨大な階乗計算をする [任意精度整数(多倍長整数)]
【Java】任意精度整数(多倍長整数)で演算する

■参考になる書籍