自然数の分割について考えてみた

• 新型のテトリスを考えていた時に自然数の分割が必要となり考えてたら結構すんなり綺麗に解けたので紹介します。

とりあえず結論

書いてみましたが、うまくまとめられなかったのでまず結論から。

この関数を用いてsplit(N,N)で解けます。コードだとこんな感じです。まんまですが。

function split(N, M) {
    if (M === 1) return 1;
    var res = 0;
    for (var k = 0; N - M * k > 0; k++) {
        res += split(N - M * k, M - 1);
    }
    return res;
}

自然数の分割とは

自然数の個数ある玉をいくつかのグループに分けます。それらのグループは区別しません。この時何通りのグループを作れますか。ただしグループには最低1つ玉がなければならず、グループは最低1つはなければなりません。

こういう問題です。言い換えると、「いくつかの自然数の和で、ある自然数を表す方法はいくつあるか、ただし交換法則、結合法則を用いると同じ式の場合は一つとみなす」という問題です。3ならば1 + 2、1 + 1 + 1、3で3つです(3を1分割すると3と考えて3も入ります)。

解く

わかりやすいので「自然数の和で、ある自然数を表す方法はいくつあるか、ただし交換法則、結合法則を用いると同じ式の場合は一つとみなす」という問題で考えます。

まず「交換法則を用いると同じならば一つとみなす」という条件について考えます。交換法則を用いると和の項をソートできます。 2 + 3 + 1 ならば 1 + 2 + 3 と。ではソートされた列のみ考えてそれらを数え上げればよいですね。

問題を解く関数を定義する

自然数NをM個の自然数または0の和で表せる数をsplit(N, M)という関数で定義します。例えば3 = 0 + 1 + 2 = 0 + 0 + 3という具合です。

このsplit関数は少し考えると問題を解く関数だとわかると思います。自然数Nを自然数の和で表し、それに必要な個数の0を加えただけですので。0の加え方は1通りの表し方に対し1通りですので対応も取れています。

関数を再帰関数として定義する

ソート済みの式を考えるのでM個の項があるとするとそれぞれが直前の項以上の値となります。

初項から順に項を決めていく時、少なくとも直前の項以上でなければならないので8を3分割していく時、初項が2ならば少なくとも 2 + 2 + 2でなければなりません。この初項以降に8 - 6、つまり2を振り分ける方法を考えればよいですね。2を初項以降の2項で分ける方法はsplit(2, 2)です。

つまり、

こう定義できます。

解答する

で答えを求めることができます。

まとめ

論理立てて考えたのですがなかなか文面に起こして説明することができませんでした。伝わらなかったらすいません。