分割数
蟻本p.66
写像12相の一つでもある。
4を4以下の自然数の足し算の合計として表す組み合わせは何通りか？
但し、「1+1+2」と「2+1+1」などは同じものとして数える。
こういう風な問題。写像12相風に言い換えると
区別しないn個の玉を区別しないk個の箱に入れる組み合わせは何通りか。
という風になる。これの解き方を考えてみる。
Wikipedia風に考えてみる
分割数の定義、p(n)
Wikipediaでの分割数の考え方（サイトごとに微妙に違うので）
自然数の和だけで、nを表す組み合わせの数（順番だけが違うものは1つとして数える）
例えばp(5)、5の分割数を考えてみる
5
4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1
p(k,n)
ここでp(k,n)という考え方を導入する…
p(k, n)=「k以上の数の和でnを表す組み合わせの数」とする(kとnの順序に注意！！)
ちょっと分かりにくいので例を挙げてみる
p(2,5) 「2以上の数の和で5を表す組み合わせ」 ＝ 2通り
5
3+2
p(3,10) 「3以上の数の足し算だけで10にする組み合わせ」＝ 4通り
10
7+3
6+4
5+5
p(100,5) 「100以上の数の足し算だけで5にする組み合わせ」＝ 0通り
無し
※$ k > nのときはどうにもならないので0通りです
p(100,100) 「100以上の数の足し算だけで100にする組み合わせ」 ＝ 1通り
100
※でしょうね
p(n) = p(1,n)
さっきのWiki式分割数の定義は
自然数の和だけで、nを表す組み合わせの数（順番だけが違うものは1つとして数える）
がp(n)です、と定義している。
よーく考えると、p(1,n)＝p(n)なことがわかる。意味が同じなので。
p(n) … 自然数の和でnを表す組み合わせの数
p(1,n)…1以上の数の和で、nを表す組み合わせの数
全く同じだ。
p(k,n) = p(k+1, n) + p(k, n-k)
ここが一番難しいと思います（個人の意見）。
p(4,10) 「4以上の数の和で10を表す組み合わせの数」は、
4を少なくとも1回使いますか？」
という場合分けをすることで、
「4を1回も使わずに4以上の数の和で10を表す組み合わせの数」
「4を少なくとも1回は使って4以上の数の和で10を表す組み合わせの数」
という風に排反した2つのパターンに分けることができます。
つまり、この2つの組み合わせを足せば求められる、ということです。
4を1回も使わずに、4以上の数の和で10を表す組み合わせの数
これは、つまり「5以上の数の和で10を表す組み合わせの数」ということですね。
元の組み合わせをp(k,n)とすると、こっちのパターンはp(k+1, n)と表せます。
4を少なくとも1回は使って、4以上の数の和で10を表す組み合わせの数
これは、「4以上の数の和で6を表す組み合わせ」のそれぞれに+4をすれば、少なくとも1回は使ったことになります。
「6」を「6+4」にする感じです。+4するかしないかの違いだけなので、組み合わせの数は前後で変わりません。
「4を少なくとも1回使って、4以上の数の和で10を表す組み合わせの数」＝ 「4以上の数の和で6を表す組み合わせの数」
つまり、p(4,6)で表せちゃうということです。p(k, n-k)で表せます。
この2つを足せば元のやつになるので、p(k,n) = p(k+1, n) + p(k, n-k)と表せます。
the 表
じっくり考えたい人のために表を用意しました。横軸がnで、縦軸がkです。m分割ですが、0を含まないです！！
table:p(k,n)
k=10 0 0 0 0 0 0 0 0 0 1
k=9 0 0 0 0 0 0 0 0 1 1
k=8 0 0 0 0 0 0 0 1 1 1
k=7 0 0 0 0 0 0 1 1 1 1
k=6 0 0 0 0 0 1 1 1 1 1
k=5 0 0 0 0 1 1 1 1 1 2
k=4 0 0 0 1 1 1 1 2 2 3
k=3 0 0 1 1 1 2 2 3 4 5
k=2 0 1 1 2 2 4 4 7 8 12
k=1 1 2 3 5 7 11 15 22 30 42
k／n n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10
蟻本p.66を解く
すいません。これまでの文章で学んできたことは、一旦捨てて下さい。すまぬ。考え方が微妙に違う。
変更点
0を含んでもOK
以上。なので、5を3分割する組み合わせは
3,1,1
2,2,1
5,0,0
4,1,0
3,2,0
みたいなバリエーションになります。
問題文
「n個の互いに区別できない品物を、m個以下に分割する方法の総数を求め、Mで割った余りを求めなさい。」
プログラミングコンテストチャレンジブック 第2版 より引用
dp[k][m] // nを、m個以下に分割する時の組み合わせの数
という風なDPテーブルを作ります。なんで逆やねんと思ってもいいです。正直遷移さえきちんとしていれば解けます。
nは品物の数、m以下に分割！という風にきちんとどのアルファベットがどの役割を果たしているのか意識しましょう。
あと、nをm以下に分割するのはp(m,n)と表すのも意識して下さい…！
p(m,n) = p(m-1, n) + p(m, n-m)について
ここで先程のような2パターンに分けるやつをします。今回は「0を一回以上使いますか？」という条件分けです。
0が一つもない…全ての数字を-1すれば、実質p(m,n-m)になる
0が少なくとも1つある…右端の0を消してしまえば、実質p(m-1,n)になる
この2つは互いに排反なので、足し合わせることで元の答えが導き出せる
いやわかんねぇよ。という人のために図です。
https://gyazo.com/7f690412e4d3abaff43820b189c047a6
この図では5を3分割するという設定です。はい。
あとは蟻本見ながら頑張って下さい…と思いましたがちょっとだけ補足です。
「-2の3分割」みたいなパターンになりうるのでは？→「マイナスが出たら0」という規約がある（Wikipedia） あとは二次元配列のサイズ(n+1とかm+1にしておく)と範囲外参照に気をつけながら、貰うDPを実装すればよいかと。