数学ガール★分割数(partition number)の漸化式と戯れる
数学ガール第一巻の最終章を飾る「分割数(partition number)」について。
数学ガールでは、分割数の母関数表現を使って、ミルカさんがいろいろと面白いテクニックを披露してくれています。これはこれでとても興味深いのですが、分割数の実際の値をコンピュータで計算する、という観点ではあんまり役に立ちません。ここでは、分割数の値を小さい方から順番に求めるために、素直に「分割数の漸化式」を考えてみることにします。
■分割数の定義
まずは分割数の定義を書いておきましょう。
0以上の整数 n の分割数 P(n) は、「nを順序を区別せずに自然数の和に分ける場合の数」で定義されます。
たとえば、P(7)は
7 6+1 5+2 5+1+1 4+3 4+2+1 4+1+1+1 3+3+1 3+2+2 3+2+1+1 3+1+1+1+1 2+2+2+1 2+2+1+1+1 2+1+1+1+1+1 1+1+1+1+1+1+1
という15通りの分割が可能なので、P(7)=15になります。
なお、P(0)=1とします。
■漸化式その１
P(n)の漸化式を考えるために、P(n)を構成する場合の数を分類してみましょう。
どういう基準で分類するのがよいか、ということですが、ここではまず「それぞれのケースの最大の数」によって分類してみることにします。P(7)の場合は、以下のように分類されます。
[最大の数が7] 7 [最大の数が6] 6+1 [最大の数が5] 5+2 5+1+1 [最大の数が4] 4+3 4+2+1 4+1+1+1 [最大の数が3] 3+3+1 3+2+2 3+2+1+1 3+1+1+1+1 [最大の数が2] 2+2+2+1 2+2+1+1+1 2+1+1+1+1+1 [最大の数が1] 1+1+1+1+1+1+1
ここで、P(n,m)を次のように定義します(n≧0, m≧1)。
P(n,m) := 整数nを順序を区別せずに「m以下の自然数」の和に分ける場合の数
定義から明らかに、P(n) = P(n,m) (n≦m)が成立します。
また、P(n)の場合の数のうち、「最大の数がm」のものの場合の数はP(n-m,m)であらわされることがわかります。
たとえば上の例で[最大の数が3]のグループに注目すると、このグループの組み合わせの数は、先頭の3を取り除いた残りの「4」を分割する組み合わせの数になるのですが、その際に各要素は「このグループの最大の数=3」を超えてはいけないので、結果、このグループの組み合わせの数は P(4,3) になります。
また、[最大の数が3][最大の数が2][最大の数が1]のグループの組み合わせの数を合計したものに注目すると、これは「7を3以下の自然数に分割する場合の数」ですから、定義によってP(7,3)になります。
ついでに、[最大の数が2][最大の数が1]のグループの組み合わせの数を合計したものに注目すると、これは「7を2以下の自然数に分割する場合の数」ですから、定義によってP(7,2)になります。
つまり、P(7,3) = P(4,3) + P(7,2) となるわけです。
一般的に書くと、
P(n,m) = P(n-m,m) + P(n,m-1) (n≧m)
となります。
初期条件も含めて正確に書くと、P(n,m) (n≧0, m≧1)の漸化式は
P(0,m) = 1 P(n,1) = 1 P(n,m) = P(n-m,m) + P(n,m-1) (n≧m＞1) P(n,m) = P(n,n) (n＜m)
のようになります。
■漸化式その２
P(n)の場合の数を、別の方法で分類してみましょう。
Q(n,r) (n≧1, r≧1)を、次のように定義します。
Q(n,r) := 整数nを順序を区別せずに「r個の自然数」の和に分ける場合の数
定義から直ちに
P(n) = Q(n,1) + Q(n,2) + ... + Q(n,n) Q(n,1) = 1 Q(n,n) = 1
がわかります。
Q(n,r)の漸化式を考えましょう。
例があったほうがわかりやすいので、Q(10,3)の組み合わせを列挙してみます。
8+1+1 7+2+1 6+3+1 6+2+2 5+4+1 5+3+2 4+4+2 4+3+3
つまり、Q(10,3)=8ということです。
ここで、それぞれの数字から1をひいたものを考えてみます。
7+0+0 6+1+0 5+2+0 5+1+1 4+3+0 4+2+1 3+3+1 3+2+2
0を省略してちょっと並び替えると
[分割の数が1] 7 [分割の数が2] 6+1 5+2 4+3 [分割の数が3] 5+1+1 4+2+1 3+3+1 3+2+2
ということで、Q(10,3)は実はQ(7,1)+Q(7,2)+Q(7,3)と同じであることがわかります。
同様の計算を Q(9,2)に対して行うと、Q(9,2)はQ(7,1)+Q(7,2)と同じであることがわかります。
これらを組み合わせると、
Q(10,3) = Q(9,2) + Q(7,3)
が成り立ちます。一般的に言うと、
Q(n,r) = Q(n-1,r-1) + Q(n-r,r)
です。
初期条件も含めて正確に書くと、P(n) (n≧0)の漸化式は
P(0) = 1 P(n) = Q(n,1) + Q(n,2) + ... + Q(n,n) Q(n,1) = 1 (n≧1) Q(n,n) = 1 (n≧1) Q(n,r) = Q(n-1,r-1) + Q(n-r,r) (n≧r≧2)
となります。
■漸化式その３
ついでに、もうひとつ漸化式を考えてみます。
漸化式その１では
P(n,m) := 整数nを順序を区別せずに「m以下の自然数」の和に分ける場合の数
としていましたが、今度は S(n,r) (n≧1, r≧1)として
S(n,r) := 整数nを順序を区別せずに自然数の和に分ける場合の数(ただし使われる自然数の最大値をrとする）
というものを考えてみます。
定義から明らかに
P(n) = S(n,1) + S(n,2) + ... + S(n,n) S(n,1) = 1 S(n,n) = 1
がわかります。
ん、Q(n,r)と同じですね。
もしかして漸化式も同じでしょうか？
ということで、「漸化式その２」と同様にS(10,3)の組み合わせを列挙してみると
3+3+3+1 3+3+2+2 3+3+2+1+1 3+3+1+1+1+1 3+2+2+2+1 3+2+2+1+1+1 3+2+1+1+1+1+1 3+1+1+1+1+1+1+1
つまりS(10,3)=8です。
ここで、先頭の3を取り払ってみると
[合計が7、最大値が3]つまりS(7,3)のもの 3+3+1 3+2+2 3+2+1+1 3+1+1+1+1 [合計が7、最大値が2]つまりS(7,2)のもの 2+2+2+1 2+2+1+1+1 2+1+1+1+1+1 [合計が7、最大値が1]つまりS(7,1)のもの 1+1+1+1+1+1+1
ということで、Q(10,3)の場合と同様、
S(10,3) = S(7,3) + S(7,2) + S(7,1)
となることがわかりました。S(7,2)+S(7,1)の部分は、同じ議論でS(9,2)と等しいことがわかりますので、一般的に言うと、
S(n,r) = S(n-1,r-1) + S(n-r,r)
となります。
漸化式も初期値も同じということなので、これはつまり
Q(n,r) = S(n,r)
ということですね。
Q(n,r) := 整数nを順序を区別せずに「r個の自然数」の和に分ける場合の数
S(n,r) := 整数nを順序を区別せずに自然数の和に分ける場合の数(ただし使われる自然数の最大値をrとする）
は、違うことを言っているように見えるのに、実は同じ値になる、ということがわかりました。
■なぜQ(n,r)とS(n,r)が同じなのか
上記のロジックをなぞれば、Q(n,r)とS(n,r)が同じになるのはわかるのですが、それぞれの定義から、これらが同じに値になる、というのはちょっとわかりづらいですね。
[Q(7,3)]（7を3個の自然数の和に分割する場合の数） 5+1+1 4+2+1 3+3+1 3+2+2
[S(7,3)]（7を自然数の和に分割する場合の数のうち、使われる自然数の最大値が3のもの） 3+3+1 3+2+2 3+2+1+1 3+1+1+1+1
ということで、確かにどちらも4になるのですが、なぜこれが一致するのでしょうか。
直感的に理解するために、定義に立ち戻って考えてみましょう。
Q(n,r)は、「n個の（区別できない）ボールを、r個の（区別できない）箱に、ボールにも箱にもあまりがないように割り当てるときの場合の数」とみなすことができます。
Q(7,3)では、7個のボールを3つの箱に割り当てるということで、横方向に3つの箱を、縦方向にボールを描いてみましょう。
そうすると、Q(7,3)は、以下のように図示することができます。
[5+1+1] ●●● ● ● ● ● [4+2+1] ●●● ●● ● ● [3+3+1] ●●● ●● ●● [3+2+2] ●●● ●●● ●
ここで、足し算の順番を縦と横で入れ替えてみましょう。
横方向は、Q(7,3)の定義によって「最大値が3」であることがわかっているので、これはまさにS(7,3)の定義に一致することがわかります。
つまり
[5+1+1] ⇔ [3+1+1+1+1] [4+2+1] ⇔ [3+2+1+1] [3+3+1] ⇔ [3+2+2] [3+2+2] ⇔ [3+3+1]
というマッピングが成立しました。
以上、直感的な説明おわりです。
■計算サンプル
おまけで、Perlによる計算のサンプルを載せておきます。
「漸化式その１」を使っています。計算量およびワークメモリ使用量は n2 に比例します。
エラーハンドリングコードは省略しているのでご注意ください。
#! /usr/bin/perl
use strict;
my %Pcache;
my $N = $ARGV[0];
my $M = $N;
$M = $ARGV[1] if ($#ARGV == 1);
printf "P(%d,%d)=%d\n", $N, $M, calcP($N, $M);
sub calcP
{
my ($n,$m) = @_;
if ($n == 0) { return 1; }
if ($m == 1) { return 1; }
if ($m > $n) { return calcP($n, $n); }
if (! defined($Pcache{$n}{$m})) {
$Pcache{$n}{$m} = calcP($n-$m, $m) + calcP($n, $m-1);
}
return $Pcache{$n}{$m};
}でわまた。
