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

2020年10月23日数学動的計画法,写像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相」で典型的な数え上げ問題のパターン総整理

Contents

1. アルゴリズム
2. 計算量
3. C++での実装例

アルゴリズム

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

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

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

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

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

二次元配列 $p$ を用意して 0 で初期化する
$p(0,0) = 1$ とする
$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;
}