n通の便せんとn通の封筒が用意されている。正しい組合せになっていない、つまり、どの便せんも間違った封筒に入れてしまった。そういう可能性は何通りあるか、というのが乱列 (derangement) という。ほかに、例として、預かった荷物がすべて間違ってn人に返された場合とか。

n個のものの乱列の数(組合せ数)をdnと書くと、その計算式は以下の通り与えられている。

derange.jpg

n=0からの乱列数は以下の通り。検証に使うといいだろう。

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, 32071101049, 481066515734, 7697064251745, 130850092279664, 2355301661033953

異なるN文字をすべてもってきて,N! 通りの異なる順列がつくれる訳だね.これらの順列ひとつひとつを辞書式順序に従って並べることができる.

<例> 異なる4文字 abcd から作られる異なる順列の数は 4! = 24 通り.それらを以下に並べる(辞書式の順).
  abcd, abdc, acbd, acdb, adbc, adcb, bacd, badc, bcad, bcda, bdac, bdca, cabd, cadb, cbad, cbda, cdab, cdba, dabc, dacb, dbac, dbca, dcab, dcba

さて,並べずに,いきなり K番目の順列はなにか,と聞かれたら答えられるか.あるいは,逆に,ある順列を見せられたら,それが何番目かはすぐに答えられるか.

上の例だと,たえば,8番目と聞かれたら,すぐに badc だ,と答えられたらOK.また,cbad は何番目? との質問に 15 番目と返事できれば合格.

コンピュータは順列や組合せの計算に非常に苦手.ちょっとでも数字が大きくなるとすぐに天文学的値になって,手に負えなくなる.4文字だけなら24通りすべてを書き出せば答えは判るけど,100文字,1000文字にもなれば,そう簡単に書く出せないだろう.

<順列総数の計算式> 高校数学の復習

  異なるN文字をすべてつかって,作れる異なる順列の総数 = N!

また,N文字のなか,同一文字がm個あるときに,これらのN文字から作れる異なる順列の総数は

  N! / m!

になる.より一般的に言うと,文字 a1 が m1個,文字 a2 が m2個,文字 a3 が m3個...含まれる場合では,

  (同じ文字を含む場合の)異なる順列の総数 = N! / (m1! m2! m3! … )

<例> aabbc から作り出せる順列は以下の通り.
  aabbc, aabcb, aacbb, ababc, abacb, abbac, abbca, abcab, abcba, acabb, acbab, acbba, baabc, baacb, babac, babca, bacab, bacba, bbaac, bbaca, bbcaa, bcaab, bcaba, bcbaa, caabb, cabab, cabba, cbaab, cbaba, cbbaa

総数は30.計算式 5!/(2! 2!) = 30 と合致する.

文字がすべて異なる場合は,上記の計算式の分母にあたる部分はすべて1になるので,同じ文字を含む計算式のほうがより一般的だといえよう.

ということで,本記事の目的は,文字の重複があってもなくても,順列の順番を正しく算出するアルゴリズムを考えることにある.

組合せ問題は得意のほうではありません.それでも問題を解かないといけないので,自己流を紹介します.真似る人はいないと思いますが,邪道であることは確かでしょう.

例で説明すると判り易いので,ほやほやの問題を取り上げます.

組合せ問題: #10884 Persephone
N 本の長さ 1m の棒でエリア(牧場)の周りを囲む.周長を N だとすると,囲むパターンは何通りあるか.

ほかにも制限条件がいくつかあるので,本文を確認されたい.結局のところ,ごちゃごちゃ余計な条件でもつけないと,出題者も計算できないのが正直なところかもしれません.あるいは,計算式に合わせて問題が作成されていたということでしょう.

さて,紙に書いて,ルール(計算式)を探るところからスタートします.
N の値が奇数の場合では囲めないことにすぐ気づきました.偶数の N=2 でもダメで,N=4で単位正方形を1つやっと作れます.N=6では回転させると,計2パターンが得られます.

N=8のケースでは答えが問題の説明文にあったので,自分で考える必要がなくなります.

N=10.問題が解けるかどうか,それにかかっていることがいままでの経験で分かっていましたので,まじめに探しました.約10分そこそこで28パターンあることに突き詰めました.

ここからは完全に自己流.いわば,ネットの力をフルに利用する訳です.オンライン整数列大辞典(米国AT&T研究所) を開いて,数字列を打ち込みます.

そのサイト,一見地味の存在ですが,知る人ぞ知る大御所.とくに組合せ問題等,手持ちの数値列の規則や数式を知りたいならば,まず一度は訪ねてみるべきところ.

さて,N=4 から N=10 までの答え 1, 2, 7, 28 を入れると,多くのシーケンスが現れてきて,ひと安心.なにも出てこないと当然答えが見つからないわけで,別な方法を考えるしかありません.

それぞれのシーケンスの名称や,コメント,参照リンク先を検討して,ターゲットを定めます.

IDナンバーA002931 は良さそうに見えますが,計算式がないので,取りあえずパス.

もっと魅力的なシーケンスは IDナンバー A005436 でした.
名称も Number of convex polygons of length 2n on square lattice というもので,いい感じ.早速そこに紹介されている計算式 a(n) = (2n+11)4^n -4(2n+1)C(2n,n) に従って,問題の入出力にある N=100 を電卓で計算してみました.残念ながら答えは合わない!

ほかのシーケンスについてもチェックしましたが,良さそうなものはなく,あきらめようかなと思いました.

ところが,Convex Polyomino というリンク先で,Convex Polyomino の分類を見ながら,今回の問題に関連性のあるものを物色していたら,上に書いた計算式の適用方法に自分が間違っていたことに気づきました.

Expanding the generating function shows that the number of convex polyominoes having perimeter 2n+8 is given by

つまり,N=100 あるいは N=50を代入するのではなく, N=46 と代入して使わないといけなかったのです.N=46に直して計算してみたら,答えが一致したので,計算式がこれでゲット.

あとは多倍長整数を使ってプログラムを書くだけ.なぜ多倍長整数が必要かというと,N=100に対応する答えは,問題の説明文に書いた通り,357215388993130669706869321408 という大きさ.30桁の値なので,現時点での Gnu C の計算できる最大整数 18446744073709551615 (=264-1),20桁) を越えてしまったからです.

具体的には,個々のN (N <= 100) について以下のように計算します.
   N = 奇数 なら,答えは 0 (ゼロ).
   N = 2以下の値なら,答えも 0.
   N = 4 なら,答えは 1.
   N = 6 なら,答えは 2.
   N = 8 以上ならば,上記の計算式に n = (N-8)/2 と代入して計算し,答えを出す.

計算式において,4のべき乗 4n と組合せ数 (2n)!/(n!*n!) についてはつぎの漸化式を使って求めます.
   4のべき乗 ⇒ F(n) = F(n-1)*4  for n >= 1
             F(0) = 1
   組合せ数 ⇒ C(n) = C(n-1) * 2(2n-1)/n  for n >= 1
            C(0) = 1

#10884 Persephone. UVa Online Judge C source program

プログラムを公開していいかどうかは少し迷いましたが,いいでしょう.どちらかというと,多倍長整数関数(このサイトですべて公開済み)の使い方は勉強になると思いますので.ちなみに,自作の多倍長整数関数は最高速とは言い切れませんが,決して遅くはありません.UVaでのスピード競争にはほとんどの場合(多倍長整数関数が必要とするケースですが)勝っていました.また,沢山のUVaプログラムに使用してきたので,関数の信頼性にも問題ないと思います.

問題をこれで解いたわけですが,数時間のプログラミング・コンテストのなかで,解けるひとがいるかどうか,とても知りたいです.コンテストですので,ネットは当然使えません.いろいろな組合せ問題の計算式をいっぱい書き込んだ参考書等を持ち込めばいいかもしれませんが,こんな書籍って存在するものでしょうか.また,多倍長整数の関数(とくに割算)が結構長いので,ソースリストを事前に用意したとしても,コンテスト会場で正しくコンピュータに打ち込むのも一苦労だろう.

余談ですが,日常 Google を使っていて,不便だなぁと感じたのはやはり数式の検索.使う変数や書き方が違っていても,数式が出てくると大変便利.どうしても無理なら,使う変数の文字や数式の構造等の入力にルールを決めてもしょうがないと思いますが,そういうサービスを期待するのは無理というものなのかな.

例えば,上の計算式.x = 0, 0.1, 0.2, 0.3, …, 300 の値について計算したいが,計算式があるのかないのか,とても知りたいのです.整数の場合の x については既に計算式は分かったけれども.

いつの日になれば,こんな式も Googling できるでしょう.

立方体の着色等の組み合わせ問題で必要な、Burnside 定理から導出された巡回置換指数 (Cycle Index) をリストアップしておく。

立方体の6面  (x16 + 3x12x22 + 6x23 + 6x12x4 + 8x32) / 24
立方体の8頂点 (x18 + 9x24 + 6x42 + 8x12x32) / 24
立方体の12辺  (x112 + 3x26 + 6x43 + 6x12x25 + 8x34) / 24

これらの式では、回転したら同じように見えるものだと同じ組合せだとカウントする。例えば、立方体の6面に、1面だけが赤でほかの5面はすべて緑の立方体は1つしかない、という具合。

ここでは、例をもって、式の使い方をデモしてみる。

1例目。立方体の8頂点を異なる2色で塗る異なる塗り方を計算してみる。2色をそれぞれ a, b で表現し、上の式 (2) に、x のところを a+b に置き換え、添え字の数字を右肩のべき乗の位置に変えると、
  ((a+b)8 + 9(a2+b2)4 + 6(a4+b4)2 + 8(a+b)2(a3+b3)2) / 24
になり、a=1, b=1 にすると、式は
  (28 + 9*24 + 6*22 + 8*22*22) / 24 = 23
になり、塗り方が23通りあることが判る。

2例目。立方体の12辺を異なる6色で塗る場合の組合せ総数。
x に a+b+c+d+e+f を代入;
  ((a+b+c+d+e+f)12 + 3(a2+b2+c2+d2+e2+f2)6 + 6(a4+b4+c4+d4+e4+f4)3 + 6(a+b+c+d+e+f)2 (a2+b2+c2+d2+e2+f2)5 + 8(a3+b3+c3+d3+e3+f3)4) / 24
a, b, c, e, d, f にそれぞれ値 1 を代入する。
 (612 + 3*66 + 6*63 + 6*62*65 + 8*64) / 24 = 90775566 通り

3例目。n色の色紙を立方体の6面に貼り付けたときにできる異なる色の立方体の数。
変数 x の中に n を直接代入しておく。(1例目や2例目のように、a, b, c 等を使って展開しても最終的に1の代入になるだけなので、その個数をカウントすれば展開結果が判るので)。
  (n6 + 3*n2*n2 + 6*n3 + 6*n2*n + 8*n2) / 24
  = (n6 + 3n4 + 12n3 + 8n2) / 24  ← ACM #10733
 つまり、n=1なら答えは1通り、n=2なら10通り、n=1000では 41666792167000000 通りの異なる色の立方体が得られるわけだ。

このように、回転を含んでいる組合せ問題は、巡回置換指数を使うと簡単に解けてしまう。マジックという言葉にぴったりの技法。

正直に申し上げて、組合せ問題には弱い。若い人と勝負しても五分五分の勝率でしかないことを考えると、本人の力はそんなものかもしれないだろう。

実用性は別として、ACM問題集に組合せ問題は割と多く出題されている。やはり得意でないひとが世の中に多いからだろう。

今回の話は、もっとも基本的な問題のひとつ。

n 個の物から r 個をとって並べる並べ方の数はいくつか。ただし、n 個の物は必ずしも異なる必要はない。また、組合せ問題なので、並べ方の順番まで考慮してはいけない。

例をもって説明すると判りやすいので、つぎのことを考えよう。

文字 A, A, B, B, C から、2文字を取り出してできる組合せは以下の通り。

  AA
  AB または BA ← 前後の順番は考えないので、AB と BA は同一と見なす。
  AC または CA
  BB
  BC または CB

つまり、5 というのが答。

一方、中学校等で、異なる n 個の物から r 個とる組合せの数について真っ先に学ぶ。つまり、上の例で考えると以下のケースに相当する。

文字 A, B, C, D, E から、2文字を取り出してできる組合せの数。(答は勿論 10 )

ほかに、異なる n 個のものから重複を許して r 個とる組合せの総数、いわゆる、重複組合せというのもある。上の例と相当するのは、

文字 A, A, A, A,…, B, B, B, …, C, C, C,… から 2個とる組合せというケース。答えを見てみると、
 
  AA
  AB または BA
  AC または CA
  BB
  BC または CB
  CC

つまり、答えは6だ。例でも判るように、重複組合せとは、文字の種類はすべて異ならなくもていいものの、文字の数は無限にあるというケース。

しかし、今回の話は、文字の種類がすべて異なっても異ならなくても、文字の数が有限の場合の組合せ問題だ。

自分の探し方が悪かったかもしれないが、Webサイトを探しても、図書を調べても、明快な回答はなかなか得られなかった。最終的に、C.L.リウの名著「組合せ数学入門 I 」に答えをやっと見つけた。

母関数を使う方法で解くという。上の例、文字 A, A, B, B, C に対応して、つぎの母関数を立てる。

  (1+x+x2) (1+x+x2) (1+x)

つまり、

  1項目の (1+x+x2) は文字 A, A に対応させる。
  2項目の (1+x+x2) は文字 B, B に対応させる。
  3項目の (1+x) は 文字 C に対応させる。

母関数を展開して、x2の前につく係数が r=2 の答えとなるという。

では展開してみるね。

  (1+x+x2) (1+x+x2) (1+x)
  = (1+x+x2 + x+x2+x3 + x2+x3+x4) (1+x)
  = (1+2x+3x2+2x3+x4) (1+x)
  = 1+x + 2x+2x2 + 3x2+3x3 + 2x3+2x4 + x4+x5
  = 1+3x+5x2+5x3+3x4+x5

確かに、x2の係数は 5、答えとなる。これだけではない、文字 A, A, B, B, C から、ゼロ文字から5文字まで取る組合せの総数はすべて母関数の展開式で判ってしまう。つまり、それぞれの係数を見れれば判るから。母関数というものは魔法みたいだと実感でき、天才数学者オイラーが母関数に魅せられたのも納得できる。

ちなみに、全て異なるn個のものに対応する母関数は

 (1+x) (1+x) … (1+x)   ← n 個
 = (1+x)n
 
になる。係数は組み合わせの公式そのものだから、その正しさは理解できよう。

また、重複組合せに対応する母関数は

 (1+x+x2+x3+…+xk+…)n = 1/(1-x)n

になる。

母関数の展開は筆算では大変だか、プログラムだとただの足し算で計算できるから、大した計算量にはならない。

最後に、ACM問題を紹介しておく。#10532 Combination! Once Again

つぎの式に、数字の前後順序を変えないで、計算の順番をはっきりさせる、括弧のつけ方は最大何通りあるか。
 1+2+3 ⇒ (1+2)+3  1+(2+3) 2通り
 1+2+3+4 ⇒ ((1+2)+3)+4  (1+2)+(3+4)  (1+(2+3))+4
         1+((2+3)+4)  1+(2+(3+4)) 計5通り

一般に、N+1個の数字を、前後の順序を変えずに結合の組合せを算出する関数は カタラン数(Catalan number) という。

カタラン数 Cnは以下の漸化式で求められる。
   C0 = 1
   Cn = Cn-1 * 2*(2n-1)/(n+1)

 C[0] = 1
 C[1] = 1
 C[2] = 2
 C[3] = 5
 C[4] = 14
 C[5] = 42
 C[6] = 132
 C[7] = 429
 C[8] = 1430
 C[9] = 4862
 C[10] = 16796
 C[11] = 58786
 C[12] = 208012
 C[13] = 742900
 C[14] = 2674440
 C[15] = 9694845
 C[16] = 35357670
 C[17] = 129644790
 C[18] = 477638700
 C[19] = 1767263190
 C[20] = 6564120420
 C[21] = 24466267020
 C[22] = 91482563640
 C[23] = 343059613650
 C[24] = 1289904147324
 C[25] = 4861946401452
 C[26] = 18367353072152
 C[27] = 69533550916004
 C[28] = 263747951750360
 C[29] = 1002242216651368
 C[30] = 3814986502092304
 C[31] = 14544636039226909
 C[32] = 55534064877048198
 C[33] = 212336130412243110
 C[34] = 812944042149730764
 C[35] = 3116285494907301262

以下はカタラン数を計算するC言語プログラム。オーバフローにならぬよう、計算途中、分母と分子との最大公約数をうまく取り除く工夫をしてある。

#include <stdio.h>
typedef unsigned long long ullong;
ullong gcd(ullong n1, ullong n2)
{
    if (n2 == 0) return n1;
    return gcd(n2, n1 2);
}
int main(void) { int i; ullong c; ullong r, bo, si;
c = 1; printf("C[0] = 1\n"); for (i = 1; i <= 35; i++) { si = c; bo = i+1; if ((r = gcd(si, bo)) > 1) { si /= r, bo /= r; } c = si*2*(2*i-1)/bo; printf("C[-655927664] = 225550331424\n", i, c); } return 0; }

さて、演算子が2種類ある場合に、話はすこしややこしくなる。
  1+2+3*4 ⇒ (1+2)+(3*4)  1+(2+3*4) 計2通り
  1*2+3*4 ⇒ (1*2)+(3*4) 1通り
と、だいぶ少なくなる。しかし、計算順位の高い演算子同士にぞれぞれの組合せを考え、さらに計算順位の低い演算子とあわせて考えると、計算結果は得られやすい。

例: 1+1+1+1+2*2+1*2*2*2+1+1+1+1*2+1 について考える。
解答: まず乗算の部分を考える
     2*2 1通り
     1*2*2*2 5通り
     1*2 1通り
つぎに、加算と合わせて考える。
      1+1+1+1+○+○+1+1+1+○+1 C9=16796通り
ただし、○は乗算の部分を表す。
それで、全体的に 1x5x1x16796=83980 通りの正しい結果が得られる。

ACM問題 #10454 Trexpression が本題に当たる。細かい説明は抜きにするが、解答プログラムを置いておく。

<数式の木表現の組合せ数を算出するプログラム> p10454.c

本題は、ハノイの塔における円盤の最小移動回数を求めるもの。他のサイトと異なるところは、塔の本数が4以上であること。

円盤がN枚あり、塔がP本ある場合、円盤の最小移動回数を M(N,P) とする。MはMoveの意。

塔が3本ある場合の最小移動回数は、よく知られているように、M(N, 3) = 2N-1 で与えられる。つまり、円盤が1枚なら1回、2枚なら3回、3枚なら7回という具合に、指数的に増える。

さて、塔が4本に増えた場合に、どう考えれば良いだろう。

話しを判りやすくするため、塔に名前A, B, C, Dをつけ、円盤を上からの小さい順にa, b, c, d, … とする。スタート状態ではすべての円盤が塔Aに集まっていて、ゴール状態では塔Dに移動したとする。

円盤が1枚。移動回数は1回で済むので、考える意味がない。M(1,4) = 1。

円盤が2枚。円盤aを塔Bに移し、円盤bを塔Dに移動。最後に円盤aを塔BからDに移し、完成する。これで、計3回の移動で済む。M(2,4) = 3。
 ここで発想を変えてみる。 上記の過程では、円盤aは M(1,4)と同じ回数で塔Bに移したと考えてよさそう。塔Dと塔Bとの違いはあるものの、本質的には同一視と考えてよさそう。円盤bは塔B以外の塔A, C, Dの3本を使って移動したので、M(1,3)の移動と考える。最後にあった、円盤aが塔Bから塔Dへの移動回数も、M(1,4)と考えられる。つまり、
    M(2,4) = M(1,4) + M(1,3) + M(1,4) = M(1,3) + 2*M(1,4) = 1 + 2*1 = 3
という漸化式が成り立つ。

円盤が3枚。ここでは上の発想を応用してみる。円盤aをM(1,4)という回数で塔Bに移動し、残り2枚の円盤bとcはM(2,3)で塔Dに移動。最後に円盤aをM(1,4)をもって塔Dに移すので、移動回数は計
    M(1,4) + M(2,3) + M(1,4) = M(2,3) + 2*M(1,4) = 3 + 2*1 = 5
になる。しかしこれでは最小移動回数であるかどうかは不明なので、円盤aとbをM(2,4)で塔Bに移し、円盤cをM(1,3)で塔Dに移し、最後に塔Bにある円盤aとbを塔Dに移してみる。この場合の移動回数は、
    M(2,4) + M(1,3) + M(2,4) = M(1,3) + 2*M(2,3) = 1 + 2*3 = 7
になる。ということで、一般的に、
    M(3,4) = min( M(2,3)+2*M(1,4), M(1,3)+2*M(2,3) ) = min(5,7) = 5
つまり、上から一枚ずつ増やした時の移動回数の中から、最小移動回数のものを使えばよい。

飛躍があるかもしれないが、一般式はつぎになるだろう。

<ハノイの塔における最小移動回数 M(N, P)>
  N: 塔の本数(3以上の整数)。 P: 円盤の数(1以上の整数)。
  M(N,1) = 1   M(N,P) = min ( M(K,P-1) + 2*M(N-K,P )  (N > 3、P > 1、K = 1,2,...,N-1)
ただし、min は最小値の意味。  初期条件: すべてのNに対し、M(N, 3) = 2N-1

上の例でもう一度検証してみる。
   M(1,4) = 1
   M(2,4) = M(1,3)+2*M(1,4) = 1+2 = 3
   M(3,4) = min { M(2,3)+2*M(1,4), M(1,3)+2*M(2,4) }
      = min { 3+2*1, 1+2*3 } = min {5, 7} = 5
   M(4,4) = min { M(3,3)+2*M(1,4), M(2,3)+2*M(2,4), M(1,3)+2*M(3,4) }
      = min { 7+2*1, 3+2*3, 1+2*5 } = min {9, 9, 11} = 9
   M(5,4) = min { M(4,3)+2*M(1,4), M(3,3)+2*M(2,4), M(2,3)+2*M(3,4), M(1,3)+2*M(4,4) }
      = min { 15+2*1, 7+2*3, 3+2*5, 1+2*9 } = min {17, 13, 13, 19} = 13
再帰的に計算してゆけばOK。

ついでに、いくつかの計算結果を書いておく。
 円盤の枚数=100、塔の本数=10 の場合の最小移動回数は 601。
 円盤の枚数=100、塔の本数=20 の場合の最小移動回数は 361。
 円盤の枚数=200、塔の本数=4 の場合の最小移動回数は 14680065。天文数字にならない。
 円盤の枚数=200、塔の本数=20 の場合の最小移動回数は 801。思ったほど少ないかな。

<追加>
塔の本数が4本の場合では、最小移動回数はと円盤の枚数との関係は以下になる。
  円盤の枚数   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, …
  最小移動回数 0, 1, 3, 5, 9, 13, 17, 25, 33, 41, 49, 65, 81, 97, 113, 129, 161, …
  前後の差     1, 2, 2, 4, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 32,
規則的に増加していく。

塔の本数が5本の場合では、最小移動回数はと円盤の枚数との関係は以下になる。
  円盤の枚数   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, …
  最小移動回数 0, 1, 3, 5, 7, 11, 15, 19, 23, 27, 31, 39, 47, 55, 63, 71, 79, 87, …
  前後の差     1, 2, 2, 2, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 16,
  つまり、     1が1個、2が3個、4が6個、8が10個、16が15個、32が21個と並んでいき、
  前後の差         2    3     4      5     6
規則的に増加していく。

<オリジナル問題>
 ハノイ塔の本数をP (4 <= p <= 50> 、円盤数をN (0 <= N <= 10000) としたときの、円盤の最小移動回数を表示せよ。
 計算制限時間 10秒。
</オリジナル問題>

<メモ> 
本題の漸化式は ACM問題 #10444 Multi-Peg Towers of Hanoi を解くために導いたもの。
 参考になるかもしれないので、#10444の解答プログラムを付しておく。

<ハノイ塔の最小移動回数を算出するプログラム> hanoi.c
 円盤枚数 0~200、塔の本数 4~20 がプログラムの入力条件。

N 個のサイコロをいっぺんにふったとき,出た目の和 K になる組合せは何通りあるか、という計算をするのが本題の内容。

簡単のようで、結構難しいようだ。例えば、5個のサイコロをふって目の和が20となるのは何通りあるか、聞かれても答えられないだろう。答は651通り。サイコロの数が2個や3個なら、テーブルをつくってコツコツやればできるだけど。

<関数を定義>
 文章で書くのが面倒だと感じた場合、数式を使って逃げるのが常識(かな)。ここでは、同じように、以下の関数を定義しておく。
 N 個のサイコロをいっぺんにふったとき,出た目の和 K になる組合せの数を 関数 S(N,K) とする。
 上の例では、S(5, 20) = 651 になる。

<漸化式の力>
 具体的な計算の仕方は私にも判らないが、組合せの計算によく使われる漸化式を利用しよう。

 S(N,K) = S(N-1,K-1) + S(N-1,K-2) + S(N-1,K-3) + S(N-1,K-4) + S(N-1,K-5) + S(N-1,K-6)

つまり、1つ目のサイコロの出た目は1~6のどれかなので、残りはN-1個のサイコロの出た目の和で算出できるわけだ。あっけない計算式だが、漸化式のパワーはこれでも認識できるだろう。

漸化式の初期条件は勿論、
 S(1,1) = S(1,2) = S(1,3) = S(1,4) = S(1,5) = S(1,6) = 1
である。

<サイコロの出た目の和を計算するプログラム> dice.c
 では、C言語プログラムを示す。Gnu Cの 64ビット整数 long long 型が使われているが、コンパイラーによっては修正が必要かもしれない。(余談だが、64ビットCPUが間もなく普及するので、128ビット整数も間もなく使えるだろう。) なお、数学的にはサイコロの数Nに上限はないが、プログラムでは N=26が上限になるようだ。それよりも大きいNだとオーバーフローになることもある。
 
プログラムの使い方は簡単、NとKの値を入力し、出力を見ればOK。
 例: N=26、K=91、出力 S(26,91) = 7766945604528200460

プログラムの応用は色々考えられるだろう。
 ・ 出た目の和がK以上の組合せ?
 ・ 出た目の和が素数になる確率?