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

数学動的計画法,写像12相,分割,分割数

以下の2つを混同しそうですが、ここでは \(p_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_1(5)=1\) (5)
  • \(p_2(5)=2\) (41, 32)
  • \(p_3(5)=2\) (311, 221)
  • \(p_4(5)=1\) (2111)
  • \(p_5(5)=1\) (11111)

のようになります。

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

アルゴリズム

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

$$p_k(n) = p_{k-1}(n-1) + p_k(n-k)$$

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

以下、2次元配列で考えやすいように \(p(n,k) := p_k(n)\) とします。

動的計画法によるアルゴリズム:

  1. 二次元配列 \(p\) を用意して 0 で初期化する
  2. \(p(0,0) = 1\) とする
  3. \(p(n,k) = p(n-1,k-1) + p(n-k,k)\) を利用して二次元配列を更新する

※ \(p(n,k) = p(n-1,k-1) + p(n-k,k)\) がどうして成立するのかは以下の2つの場合を考えると分かります。

  • 分割したときに 1 が存在する場合:あらかじめ 1 を分けておいて、残りの \(n-1\) を \(k-1\) 個に分ければ良いので、\(p(n-1,k-1)\) 通り
  • 分割したときに全ての数が 2 以上の場合:先に \(k\) を 1 つずつ分けてしまえば、あとは \(n-k\) を \(k\) 個に分ければ良いので \(p(n-k,k)\) 通り

計算量

  • \(O(nk)\)

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

C++での実装例

AOJ DPL_5_L Balls and Boxes 12 を解く実装例です。\(p_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 = 1; n < N + 1; n++) {
        for (long long k = 1; k < K + 1; k++) {
            if (n - k >= 0) {
                p[n][k] = (p[n - 1][k - 1] + p[n - k][k]) % MOD;
            } else {
                p[n][k] = p[n - 1][k - 1];
            }
        }
    }

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

    return 0;
}