自然数nをk個の0以上の整数に分割する方法の総数を求めるアルゴリズム

2020年10月23日数学動的計画法,写像12相,分割,分割数

以下の2つを混同しそうですが、ここでは \(p_{\leq k}(n)\) を求めることを考えます。

• \(p_k(n)\) : 自然数 \(n\) を \(k\) 個の 1 以上の整数に分割する方法の数。言い換えると、区別できない \(n\) 個の要素を区別できない \(k\) 個ちょうどのブロックに分割する方法の数
• \(p_{\leq k}(n)\) : よく \(P(n,k)\) とも書く。自然数 \(n\) を \(k\) 個の 0以上の整数に分割する方法の数。言い換えると、区別できない \(n\) 個の要素を区別できない高々 \(k\) 個のブロックに分割する方法の数

例えば、\(n=5\) の時を考えると “5, 41, 32, 311, 221, 2111, 11111" の7通りの分割の仕方があり、

• \(p_{\leq 1}(5)=1\)
• \(p_{\leq 2}(5)=1+2=3\)
• \(p_{\leq 3}(5)=1+2+2=5\)
• \(p_{\leq 4}(5)=1+2+2+1=6\)
• \(p_{\leq 5}(5)=1+2+2+1+1=7\)

のようになります。

特に、\(p_{\leq n}(n)\) は \(P(n)\) と書くことも多く、これを分割数と呼びます。

※ \(p_{\leq k}(n)\) は「写像12相」と呼ばれるものを通して学ぶと、他の数え上げ問題との関わりが分かり全体像がスッキリします。ぜひ確認してみることをおすすめします。
「写像12相」で典型的な数え上げ問題のパターン総整理

アルゴリズム

二次元配列で考えやすいように、\(P(n,k):=p_{\leq k}(n)\) として書くことにします。

以下の漸化式が成立することが知られています。

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

これを利用して、動的計画法により計算することが可能です。

※ \(P(n,k) =P(n,k-1) +P(n-k,n)\) がなぜ成立するかは以下の2通りに場合分けしてみると分かります。

• 分割に 0 を含む場合：その 0 を取り除いて、\(n\) を残りの \(k-1\) 個に分割することを考えれば良いので、\(P(n,k-1)\) 通り
• 分割に 0 を含まない場合：全ての分割は 1 以上となっているので、あらかじめ 1 を \(k\) 個分割しておくことを考えると、残りは \(n-k\) を \(k\) 個に分割することを考えれば良い。よって \(P(n-k,k)\) 通り

ちなみにですが \(P(n,k)=\sum_{i=0}^{x}p_i(n)\) を利用することで、計算することも可能です。

計算量

• \(O(nk)\)

動的計画法により \(n \times k\) のテーブルを更新することになります。1回あたりの更新は定数時間なので、\(O(nk)\) だけかかってしまいます。

C++での実装例

AOJ DPL_5_J Balls and Boxes 10 を解く実装例です。\(p_{\leq k}(n)\) を計算します。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;  // 素数

int main() {
    long long N, K;
    cin >> N >> K;

    vector<vector<long long>> P(N + 1, vector<long long>(K + 1, 0));
    P[0][0] = 1;

    for (long long n = 0; n < N + 1; n++) {
        for (long long k = 1; k < K + 1; k++) {
            if (n - k >= 0) {
                P[n][k] = (P[n][k - 1] + P[n - k][k]) % MOD;
            } else {
                P[n][k] = P[n][k - 1];
            }
        }
    }

    cout << P[N][K] << endl;

    return 0;
}