こないだのドワンゴからの挑戦状で、分割数を用いる問題が出題されたので、周辺の話題を整理してみました。

数え上げに関する話題として分割数やスターリング数は時折登場しますが、どちらも写像12相と呼ばれる広い枠組みに含まれています。今回は分割数を、次の記事でスターリング数を勉強します。

なお、分割数 (の考え方) が使える問題として以下があります：

写像12相

n 個の玉を k 個の箱に入れる場合の数を数える問題を考えます。

玉をそれぞれ区別するか
箱をそれぞれ区別するか
各箱に入る玉の個数は「制限なし」「1個以内」「1個以上」

によって12パターンの問題設定が考えられるので写像12相と呼ばれています。以下の記事にとてもよくまとまっています。

mathtrain.jp

ちょっと問題設定がなかなかピンと来ない感じですが、今回は「箱を区別しない」部分をメインに考えます。「箱を区別しない」というのはつまり n 個の玉を k 個のグループに分ける問題を考えるということです。

1. 分割数

蟻本第二版の P. 66 に載っています。考察の対象は以下の場合です:

n 個の玉は区別しない
k 個の箱は区別しない
各箱に入る玉の個数に制限はない

つまり自然数 n を k 個の 0 以上の整数の和で表す場合の数 (順序が異なるものは同一視) です。n = 5, k = 3 であれば、

0 + 0 + 5 = 0 + 1 + 4 = 0 + 2 + 3 = 1 + 1 + 3 = 1 + 2 + 2

の 5 通りの表し方があります。この場合の数を P(n, k) と置くことにします。 P(n, k) は「自然数 n を k 個以下の 1 以上の整数の和で表す場合の数」とも言い換えられます (蟻本ではこっち)

分割数の性質

ここにまとめます。

「k 個の 1 以上の整数への分割」は P(n-k, k) 通り
「何個でもよい 1 以上の整数への分割」は P(n, n) 通り
P(n, k) = P(n, k-1) + P(n-k, k)
(ついでに) P(n, n) は O(n√n) で求められる

このうち、3 番目の漸化式を用いることで、P(n, k) を O(nk) で計算できます。特に P(n, n) は O(n²) で計算できます。さらに P(n, n) を求めるだけならばより高速に O(n√n) で計算できるようです。

なお、先程の写像12相の記事では、各箱に入る玉の個数が 1 個以上である場合を P(n, k) としているので記号の使い方が微妙に異なりますが、本質的にほとんど一緒です。

「k 個の 1 以上の整数への分割」は P(n-k, k) 通り

P(n, k) が求まれば、写像12相のうちの

n 個の玉は区別しない
k 個の箱は区別しない
各箱に入る玉の個数は 1 個以上

も簡単に求まります。つまり自然数 n を k 個の 1 以上の整数の和で表す場合の数です。これを Q(n, k) と置くことにします。Q(n, k) に対して、n を分割した k 個の値それぞれについて 1 引くことで、

Q(n, k)  
= (n を k 個の 1 以上の整数に分割する場合の数)  
= (n - k を k 個の 0 以上の整数に分割する場合の数)  
= P(n-k, k)

が成立します。この考察が「分割数の漸化式」の理解に直結します。

漸化式 P(n, k) = P(n, k-1) + P(n-k, k)

P(n, k) = P(n, k-1) + P(n-k, k)

の導出です。n を k 個の 0 以上の整数の和へと分割する方法のうち

0 を含むもの:
0 が何個あるかはわからないが、そのうちの 1 個の 0 を取り除いてしまってもよくて、残りの k - 1 個の 0 以上の整数の和で n を表す方法を考えればよい。よって、P(n, k-1) 通り。

0 を含まないもの:
n を k 個の 1 以上の整数に分割する場合の数、つまり Q(n, k) なので、P(n-k, k) 通り。　

以上より、P(n, k) = P(n, k-1) + P(n-k, k) が成立します。
一瞬、前者の場合について、0 が複数ある場合にダブルカウントしてしまってそうで怖くなるのですが、今回は k 個の整数は区別できないので大丈夫です。

1-3. 分割数を用いる問題

yukicoder No.269 見栄っ張りの募金活動

N 人の生徒で順に寄付金を払っていくことで合計 S 円の寄付金を集めたいが、 i + 1 人目の生徒は i 人目の生徒よりも K 円以上多く支払っていなければならない。このようなことが成立する場合の数を求める問題。

様々な解法がある模様ですが、分割数でも解けます。

x[ i ] := (i 人目の生徒の支払う金額) - iK

とすると、

・x[0] + x[1] + ⋯+x[N-1] = S−(K+2K+⋯+(N-1)K)
・0 <= x[0] <= x[1] <= ... <= x[N-1]

を満たす (x[0], x[1], ..., x[N-1]) の組を数え上げる問題になるので、これは分割数 P(S−(K+2K+⋯+(N-1)K), N) です。
　

第4回ドワンゴからの挑戦状予選 C - Kill/Death

これも様々な解法があるようですが、分割数を前処理で求めておいてそれを利用して DP するのが1つの解法かと思います。
　

AOJ 0537 Bingo

分割数そのものではないですが関連しています。想定解法よりオーダーレベルで速い解法です。怒髪さんの【No.027】「AOJ 0537 Bingo」 - dohatsutsu’s diary を参考にしました。 k = N², n = S - k(k+1)/2, m = M-k として、

・x[0] + x[1] + ... + x[k-1] = n
・ 0<= x[0] <= x[1] <= ... <= x[k-1] <= m

を満たす (x[0], x[1], ..., x[k-1]) の組を数え上げる問題に帰着します。各 x が m 以下であるという条件の加わった分割数です。分割数を求める DP と同様にして求められます。P'(n, k) と置くことにします。

0 を含むもの:
分割数とまったく同様に、P'(n, k-1) 通り。

0 を含まないもの:
(n を k 個の 1 以上 m 以下の整数に分割する場合の数)
= (n-k を k 個の 0 以上 m-1 以下の整数に分割する場合の数)
= (n-k を k 個の 0 以上 m 以下の整数の分割する場合の数) - (そのうち m を含む場合の数)

この (そのうち m を含む場合の数) は m を 1 個取り除いてしまっても一緒なので P'(n-k-m, k-1) 通りです。まとめると、

P'(n, k) = P'(n, k-1) + P'(n-k, k) - P'(n-k-m, k-1)

で求められます。
　

CSA 032 G Sum of Powers

a[0] + a[1] + ... + a[K-1] = N を満たす正の整数の組 (a[0], a[1], a[K-1]) それぞれに対して a[0]^M + a[1]^M + ... + a[K-1]^M の値を考えて、その総和を 1000000007 で割った余りを求める問題。

分割数の使い方がすごく賢い。 CSAcademy Round #32 : G. Sum of Powers - kmjp's blog に詳細あり。

総和が N になる a のうち、各 x が y 回使われるものが何通りあるかが計算できればよい。

総和が N になる a のうち、x が y 回以上使われるものは、P(N- K - xy, K - y) 通りあることがわかるので、x が y 回使われるものは P(N - K - (x-1)y, K - y) - P(N - K - (x-1)*(y + 1), K - (y + 1)) 通りある。

2. スターリング数

書きました drken1215.hatenablog.com

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

分割数と、問題まとめ

写像12相