プログラミングコンテストチャレンジブックの分割数について

「分割数」でぐぐると同様の記事がいろいろ出てくるのだけれど、やっぱりよく分からなかったので考えたらようやっと納得がいった。なので、その記録をしておく。

まず、なんだか分からなかった原因は、「jのi分割数」というのは「jを1以上の自然数i個の和でかきあらわしたときの(順序を無視した)書き表しかたの個数」であるはずなのに、0の和も考えているようにも読めて何を考えているのだかよく分からなくなるところにあったと思う。そういうわけで、式と向き合っていたところ意図がわかった。

「jのi分割」は「jを1以上の自然数i個の和でかきあらわしたときの(順序を無視した)書き表しかた」で、これらのなす集合である「jのi分割のなす集合」を考える。
この集合を、「jのi分割のなす集合のうち、2以上のみを(1個以上)使うもの」と「jのi分割のなす集合のうち、1を(1個以上)使うもの」の2つに分ける。
すると、この2つの部分集合は交わりがなく、しかもこの2つの集合の結びは「jのi分割のなす集合」となるので、「jのi分割数」であるdp[i][j]を求めるには、この2つの部分集合それぞれの元の個数を数えればよい。

まず、「jのi分割のなす集合のうち、2以上のみを(1個以上)使うもの」の個数を考える。実は、「jのi分割のなす集合のうち、2以上のみを(1個以上)使うもの」と「(j-i)のi分割のなす集合」との間には同型対応が作れる(つまり、余りもダブりもなく、2つの集合から1つずつ選んできたペアを作ることができる)。具体的にどうするかというと、「jのi分割のなす集合のうち、2以上のみを(1個以上)使うもの」の元「2を $a_2$ 個、3を $a_3$ 個、…」に対して*1「1を $a_2$ 個、2を $a_3$ 個、…」と割り当てる。いま、i分割を考えていることから、 $a_2+a_3+\dots = i$ が成り立っており、この対応は確かにi分割をi分割に写している。さらに、jの分割を考えていることから $\sum_{i\ge 2} i a_i = j$ となっており、よって $\sum_{i\ge 2} (i-1)a_{i}= \sum_{i\ge 2} i a_i - \sum_{i\ge 2} a_i = j - i$ となる。よって、確かにjの分割を(j-i)の分割に写している。以上のことより、この対応は確かに「jのi分割のなす集合のうち、2以上のみを(1個以上)使うもの」から「(j-i)のi分割のなす集合」への写像になっている。逆の対応は明らかなので省略し、それが全単射になっていることも省略する*2。よって、「jのi分割のなす集合のうち、2以上のみを(1個以上)使うもの」の個数はdp[i][j-i]である。

次に、「jのi分割のなす集合のうち、1を(1個以上)使うもの」の個数を考える。「jのi分割のなす集合のうち、1を(1個以上)使うもの」は、その使っている1を取り除いて考えれば「jの(i-1)分割」になり、逆の対応もつけることができて同型であることがわかる。よって、「jのi分割のなす集合のうち、1を(1個以上)使うもの」の個数は「jの(i-1)分割」の個数であり、これはdp[i-1][j]である。

以上で、dp[i][j] = dp[i][j-i] + dp[i-1][j]である。

集合の分け方が一番のミソでした。

*1:「2以上のみを～」という定義から、「1を0個」使っているということに注意。つまり、「1を $a_1$ 個～」と書く必要はない。