Partition HOWTO (日本語版)

この HOWTO は NZMATH で数の分割を使う方法を説明するものです。 注意として、一部の機能は次期リリースに含まれる予定のもので、現在のリリースバージョンには含まれていないということです。 もし、ここでの説明が気に入って次期リリースに先行して使ってみたいという方は、sourceforge.net で公開されている mercurial のリポジトリを clone して下さい。

% hg clone http://nzmath.hg.sourceforge.net:8000/hgroot/nzmath/nzmath

1. 数の分割

自然数 n の分割とは、n を自然数の和として表すことである。 たとえば、2+2+1 は 5 の分割の一つである。 足し算は順番を変えても結果が同じなので、現れる数の順番は気にしないことにする。 つまり 2+2+1 と 2+1+2 と 1+2+2 は区別しない。 このような数の分割は、組合せ構造を考えるときにしばしば現れる。 そこで NZMATH では combinatorial モジュールに関連する関数が収められている。 以下の例では from nzmath.combinatorial import * してあると仮定する。

まず分割そのものを得るには partition_generator を使う。

>>> for partition in partition_generator(5):
...     print partition
...
(5,)
(4, 1)
(3, 2)
(3, 1, 1)
(2, 2, 1)
(2, 1, 1, 1)
(1, 1, 1, 1, 1)
>>>

これが 5 の分割の全てである。 足し算の式を返すのではなく、足される数のタプルが返るようになっている。

ここで7個の分割が現れたが、n を 5 から増やすとどれぐらい分割の個数は増えるだろう、 と疑問に思うかもしれない。 原理的には len(list(partition_generator(n))) で求められるが、 これは非効率的であり、この個数(分割数という)だけ求める方法がある。

>>> partition_number(6)
11
>>>

この関数はこの HOWTO では以降使わない。 分割数の増え方はほぼ指数的である。

2. 上限付き分割

今度は足される数に上限がある場合を考えてみよう。 つまり 5 の分割の内、たとえば足される数が3以下のものだけ得たいという場合にどうするかである。 単純に要らないものを捨てるならばこう書けばよいだろう。

>>> for partition in partition_generator(5):
...     if all(d <= 3 for d in partition):
...         print partition
...
(3, 2)
(3, 1, 1)
(2, 2, 1)
(2, 1, 1, 1)
(1, 1, 1, 1, 1)
>>>

この手のフィルタリングは間違いではない。 というより、一般的に他に手段がないのならこれがベストだろう。 しかし、この節は次のことを言うためにある: 「partition_generator には第2引数が渡せます」

>>> for partition in partition_generator(5, 3):
...     print partition
...
(3, 2)
(3, 1, 1)
(2, 2, 1)
(2, 1, 1, 1)
(1, 1, 1, 1, 1)
>>>

3. 個数に上限のある分割

次は足される個数に上限がある場合を考えよう。 5 の分割の中で足される個数が3個以下のものが欲しい、と。 再び、まずは一般的な手法から。

>>> for partition in partition_generator(5):
...     if len(partition) <= 3:
...         print partition
...
(5, )
(4, 1)
(3, 2)
(3, 1, 1)
(2, 2, 1)
>>>

さて、先ほどの3以下のものの個数が5個、この足される個数3個以下のものも5個。 これは偶然ではない。 即ち、これらの間には共役と呼ばれる一対一対応がある。 この対応は図形的に見ると解り易い(ヤング図形またはフェラーズ図形と呼ばれる)。 下図の左が (4, 1) 右が (2, 1, 1, 1) である。

. . . .    . .
.          .
           .
           .

点を横に数えると左は上から4,1。 右は上から 2,1,1,1 である。 共役はこの図形を裏返す操作である。 左上の角を固定して、右のものを下に持ってくるようにひっくり返す。 (4, 1) はこの操作で (2, 1, 1, 1) と重なるのが見て取れると思う。

NZMATH には partition_conjugate という関数がある。

>>> for partition in partition_generator(5, 3):
...     print partition_conjugate(partition)
...
(2, 2, 1)
(3, 1, 1)
(3, 2)
(4, 1)
(5,)
>>>

先ほどと順番が異なる(たまたま逆になった)が、同じ分割が出てくる。

4. ちょうど k 以下への分割

今までの節は既に定義されている関数の紹介に過ぎなかったが、ここからは必要に応じて組み立てるやり方である。 partition_generator の第2引数を使うことで「高々 k」の部分に分割する方法は学んだが、では、一番大きい部分が「ちょうど k」となる分割を考えよう。フィルターする戦略はここでも有効であるが、少し考えると無駄になる分割を一切生成せずに済ませることができることが解る。 即ち「ちょうど k」の部分は全ての必要な分割に共通することに着目する。 すると、残る n-k を高々 k の部分に分割したものと一緒にする(接ぐ)ことで、 最大がちょうど k の分割が得られる。

# n=6, k=3
>>> for partition in partition_generator(6-3, 3):
...     print (3,)+partition
...
(3, 3)
(3, 2, 1)
(3, 1, 1, 1)
>>>

問題: n をちょうど k 個の部分に分割する方法を考えよ。 (ヒント: 共役を用いよ)

5. 最小を制限された分割

最大を制限する方法は既に学んだが、では最小を制限するにはどうすればよいだろう。 たとえば、「少なくとも 2」の部分への 7 の分割というような問題である。 ここでも共役を考えるのがよいだろう。 少なくとも 2 の部分への分割は、少なくとも二つの最大部分を持つ分割の共役である。 するとこれは前節の拡張である。

>>> n=7; k=2
>>> for m in range(1, n//k + 1):
...     for partition in partition_generator(n - m*k, m):
...         print (m,)*k + partition:
... 
(1, 1, 1, 1, 1, 1, 1)
(2, 2, 2, 1)
(2, 2, 1, 1, 1)
(3, 3, 1)
>>>

得たいのはこれの共役であったから、

>>> n=7; k=2
>>> for m in range(1, n//k + 1):
...     for partition in partition_generator(n - m*k, m):
...         print partition_conjugate((m,)*k + partition):
... 
(7,)
(4, 3)
(5, 2)
(3, 2, 2)
>>>

6. 奇数部分への分割

最大・最小の制限は大体理解できてきたと思うので、次は大きく方向を変えて、奇数部分への分割を考えよう。 たとえば 9 の奇数部分への分割は

(9,)
(7, 1, 1)
(5, 3, 1)
(5, 1, 1, 1, 1)
(3, 3, 3)
(3, 3, 1, 1, 1)
(3, 1, 1, 1, 1, 1, 1)
(1, 1, 1, 1, 1, 1, 1, 1, 1)

である。9 の分割は全部で30個あるが、その内奇数部分への分割は8個だけである。 この差を考えればフィルター的な作り方は避けたい。

9 = 2*5 - 1
7 = 2*4 - 1
...
1 = 2*1 - 1

という対応で 2N+1 (奇数) と N (自然数) を対応づけると、

(9,)                        ⟷ (5,)
(7, 1, 1)                   ⟷ (4, 1, 1)
(5, 3, 1)                   ⟷ (3, 2, 1)
(5, 1, 1, 1, 1)             ⟷ (3, 1, 1, 1, 1)
(3, 3, 3)                   ⟷ (2, 2, 2)
(3, 3, 1, 1, 1)             ⟷ (2, 2, 1, 1, 1)
(3, 1, 1, 1, 1, 1, 1)       ⟷ (2, 1, 1, 1, 1, 1, 1)
(1, 1, 1, 1, 1, 1, 1, 1, 1) ⟷ (1, 1, 1, 1, 1, 1, 1, 1, 1)

右側を眺めると、次のような対応が見て取れる。 5 のちょうど1個への分割、6 のちょうど3個への分割、…、9 のちょうど9個への分割を集めてきたものと対応がつく。 ちょうど k 個への分割は4節の問題として提示した。 これが利用できる。

>>> n = 9
>>> for m in range(n//2 + 1, n + 1):
...     for partition in partition_generator(n - m, 2*m - n):
...         print tuple(2*x - 1 for x in partition_conjugate((2*m - n,) + partition))
... 
(9,)
(3, 3, 3)
(5, 3, 1)
(7, 1, 1)
(3, 3, 1, 1, 1)
(5, 1, 1, 1, 1)
(3, 1, 1, 1, 1, 1, 1)
(1, 1, 1, 1, 1, 1, 1, 1, 1)
>>> 

問題: 奇数部分への分割は互いに相異なる部分への分割に「同じ部分があればその二つを融合した部分を作る」という規則を繰り返し適用することで一対一に対応づけられる。このことを利用して互いに相異なる部分への分割を実現せよ。

7. 結語

単純な分割から、いくつかの制限を付けた分割を作る方法を説明した。 最後の方は専用のジェネレータを作った方が楽そうであるが、適当な一対一対応により無駄なく生成できることが見て取れたと思う。 専用のジェネレータを作る方法は HOWTO 第2部で紹介する。

以下の文献を参照した: アンドリュース/エリクソン「整数の分割」数学書房