８章　分割数　再び

３章で紹介した分割数 p(n)＝p_n は、以下の母関数によって定義される。

p₀＋p₁x＋p₂x²＋……

＝ ∞
Σ
n=0 p_nxⁿ 　

＝ ∞
Π
n=1 1
------
(1－xⁿ) 　

＝ 1
-----------------------
(1－x)(1－x²)(1－x³) ・……

（０の分割数は、便宜上１と定義する。）

よって、７章で求めた無限乗積と、『数学者の密室』11章　数論的アルゴリズム
６．形式べき級数の係数決定で示した方法で、分割数を計算することができる。

まず、無限乗積 (1－x)(1－x²)(1－x³)・…… を、

＝a₀＋a₁x＋a₂x²＋……

とする。

(p₀＋p₁x＋p₂x²＋……) (a₀＋a₁x＋a₂x²＋……)＝１

の左辺を展開すると、

０次：p₀a₀＝１
１次：p₁a₀＋p₀a₁＝０
２次：p₂a₀＋p₁a₁＋p₀a₂＝０

　…………

ｋ次：p_ka₀＋p_k-1a₁＋……＋p₀a_k＝０

∴ p_k＝－1/(a₀)・(p_k-1a₁＋……＋p₀a_k)

a₀＝１だから、

∴ p_k＝－p_k-1a₁－……－p₀a_k

これを、前の章のマクロの中に追加する。
マクロは、以下のようになる。

分割数を計算するためのマクロ。

Sub Record3()
    Worksheets("Sheet3").Activate

    Dim a(10), w(10), p(10)
    k = 10

    Cells(1, 1).Value = "n"
    Cells(1, 2).Value = "a(n)"
    Cells(1, 3).Value = "p(n)"

    a(0) = 1: a(1) = -1
    For i = 2 To k
        For j = i To k: w(j) = a(j) - a(j - i): Next j
        For j = 2 To k: a(j) = w(j): Next j
    Next i

    p(0) = 1
    For i = 1 To k
        For j = 0 To i - 1: p(i) = p(i) - p(j) * a(i - j): Next j
    Next i

    For i = 0 To k
        Cells(i + 2, 1).Value = i
        Cells(i + 2, 2).Value = a(i)
        Cells(i + 2, 3).Value = p(i)
    Next i

End Sub

実行結果は以下のとおり。

　A　　B　　C　

1 n a(n) p(n)

2 0 1 1

3 1 -1 1

4 2 -1 2

5 3 0 3

6 4 0 5

7 5 1 7

8 6 0 11

9 7 1 15

10 8 0 22

11 9 0 30

12 10 0 42

	A	B	C
1	n	a(n)	p(n)
2	0	1	1
3	1	-1	1
4	2	-1	2
5	3	0	3
6	4	0	5
7	5	1	7
8	6	0	11
9	7	1	15
10	8	0	22
11	9	0	30
12	10	0	42

３章の結果と比較すると、確かにあっている。

それでは、桁あふれしない程度までｋの値を大きくして、100以下の分割数を求めてみよう。
結果は以下のようになる。

n p(n) n p(n) n p(n) n p(n) n p(n)

1 1 21 792 41 44583 61 1121505 81 18004327

2 2 22 1002 42 53174 62 1300156 82 20506255

3 3 23 1255 43 63261 63 1505499 83 23338469

4 5 24 1575 44 75175 64 1741630 84 26543660

5 7 25 1958 45 89134 65 2012558 85 30167357

6 11 26 2436 46 105558 66 2323520 86 34262962

7 15 27 3010 47 124754 67 2679689 87 38887673

8 22 28 3718 48 147273 68 3087735 88 44108109

9 30 29 4565 49 173525 69 3554345 89 49995925

10 42 30 5604 50 204226 70 4087968 90 56634173

11 56 31 6842 51 239943 71 4697205 91 64112359

12 77 32 8349 52 281589 72 5392783 92 72533807

13 101 33 10143 53 329931 73 6185689 93 82010177

14 135 34 12310 54 386155 74 7089500 94 92669720

15 176 35 14883 55 451276 75 8118264 95 104651419

16 231 36 17977 56 526823 76 9289091 96 118114304

17 297 37 21637 57 614154 77 10619863 97 133230930

18 385 38 26015 58 715220 78 12132164 98 150198136

19 490 39 31185 59 831820 79 13848650 99 169229875

20 627 40 37338 60 966467 80 15796476 100 190569292

n	p(n)	n	p(n)	n	p(n)	n	p(n)	n	p(n)
1	1	21	792	41	44583	61	1121505	81	18004327
2	2	22	1002	42	53174	62	1300156	82	20506255
3	3	23	1255	43	63261	63	1505499	83	23338469
4	5	24	1575	44	75175	64	1741630	84	26543660
5	7	25	1958	45	89134	65	2012558	85	30167357
6	11	26	2436	46	105558	66	2323520	86	34262962
7	15	27	3010	47	124754	67	2679689	87	38887673
8	22	28	3718	48	147273	68	3087735	88	44108109
9	30	29	4565	49	173525	69	3554345	89	49995925
10	42	30	5604	50	204226	70	4087968	90	56634173
11	56	31	6842	51	239943	71	4697205	91	64112359
12	77	32	8349	52	281589	72	5392783	92	72533807
13	101	33	10143	53	329931	73	6185689	93	82010177
14	135	34	12310	54	386155	74	7089500	94	92669720
15	176	35	14883	55	451276	75	8118264	95	104651419
16	231	36	17977	56	526823	76	9289091	96	118114304
17	297	37	21637	57	614154	77	10619863	97	133230930
18	385	38	26015	58	715220	78	12132164	98	150198136
19	490	39	31185	59	831820	79	13848650	99	169229875
20	627	40	37338	60	966467	80	15796476	100	190569292

ｋは、269までは桁あふれしないようである。

UBASICを使えば、BASEの変更で、配列としてとれる範囲まで分割数を求めることができる。
例えば、１万以下の分割数計算、というのも夢ではない。

前頁	目次	次頁

E-mail : kc2h-msm@asahi-net.or.jp

三島　久典

＝	∞ Σ n=0	p_nxⁿ
＝	∞ Π n=1	1 ------ (1－xⁿ)
＝	1 ----------------------- (1－x)(1－x²)(1－x³) ・……

８章 分割数 再び

８章　分割数　再び