勝手に考えた分断数について

前回記事で、勝手に「分断数」なるものを考えました（「分割数」参照）

この分断数について考えてみたいと思います。

分割とは、（正の）整数を自然数（正の整数）の和で表したものです。同じ自然数を重ねて使ってもいいですが、並べる順番が違っているものは同じ分割と見なされるます。

これに対して、勝手に名付けた「分断」は、（正の）整数を自然数（正の整数）の和で表したもので、同じ自然数を重ねて使ってもいいし、並べる順番が違っていれば異なる分断とします。

5の分割数P5と分断数Q5をそれぞれ具体的にみると、

分割数P5=7
5=5
5=4+1
5=3+2
5=3+1+1
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

分断数Q5=16
5=5
5=4+1
5=3+2
5=2+3
5=1+4
5=3+1+1
5=2+2+1
5=2+1+2
5=1+3+1
5=1+2+2
5=1+1+3
5=2+1+1+1
5=1+2+1+1
5=1+1+2+1
5=1+1+1+2
5=1+1+1+1+1

となります。

この分断数の一般項Qnを求めてみようという試みです。

何度も書きますが、「分断数」というのは私が勝手に作った用語です。ひょっとしたら、数学で適切な用語があるのかもしれませんが、私は知らないので、とりあえず分断数で進めていきます。



分断数をQnとし、n=0から順に確認してみます。前回記事「分割数」での書き方にならって書いていきます。

n=0のときは、「分断しない」という方法が一つだけあります。

0=0

したがって、

Q0=1

です。

n=1のときは、これも分断できません。

1=1

つまり、1通りなので、

Q1=1

n=2のときは、「分断しない」と「1と1に分断する」という2通りです。

2=2
2=1+1

つまり、

Q2=2

n=3の場合は、

3=3
3=2+1
3=1+2
3=1+1+1

の4通り。

Q3=4

n=4の場合は、

4=4
4=3+1
4=2+2
4=1+3
4=2+1+1
4=1+2+1
4=1+1+2
4=1+1+1+1

の8通りなので、

Q4=8

ここまで来ると、ある程度法則が浮かんできます。

n=5を例にとると、

5=5

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

5=3+1+1
5=2+2+1
5=2+1+2
5=1+3+1
5=1+2+2
5=1+1+3

5=2+1+1+1
5=1+2+1+1
5=1+1+2+1
5=1+1+1+2

5=1+1+1+1+1

わかりやすく行間を空けてみました。5の分断の方法として、

「分断しない」で1通り
「2つの数に分断」で4通り
「3つの数に分断」で6通り
「4つの数に分断」で4通り
「5つの数に分断」で1通り

合計16通りとなります。

もう少しわかりやすくすると、次のように表現できそうです。

5=11111

5=1111｜1
5=111｜11
5=11｜111
5=1｜1111

5=111｜1｜1
5=11｜11｜1
5=11｜1｜11
5=1｜111｜1
5=1｜11｜11
5=1｜1｜111

5=11｜1｜1｜1
5=1｜11｜1｜1
5=1｜1｜11｜1
5=1｜1｜1｜11

5=1｜1｜1｜1｜1

5を5つの数に分断（つまり5=1+1+1+1+1）する場合、分断の線（｜）は4つあります。その分断されうる可能性のあるところから分断線を選択したときの組み合わせを考えます。すると、

4つのうち0本の分断線を選択：4Ｃ0=1
4つのうち1本の分断線を選択：4Ｃ1=4
4つのうち2本の分断線を選択：4Ｃ2=6
4つのうち3本の分断線を選択：4Ｃ3=4
4つのうち4本の分断線を選択：4Ｃ4=1

これらを合計したものが、5の分断数となります。

Ｃ（組み合わせ；コンビネーション）の公式は覚えていないので、Wikipediaで調べました…。

単純な場合で、異なるn個のものから異なるm個のものを選ぶ（このとき必然的にn≥mなる非負整数でなければいけないが, このほかには何の制限も課されない）組合せというのを考えると、その選び方の総数はよく知られており、Combinationの頭文字を取って、しばしばnCmまたはC(n,m)のような記号を使って表される。
nＣm = {n×(n-1)×(n-2)×…×(n-m-1)}/{m×(m-1)×…×1｝

高校（中学校？）の授業では、階乗の式で覚えていた記憶があるので、こっちの方が計算しやすいかな？

nＣm = n!/{m!(n-m)!}

今、Q5について考えると、

Q5 = 4Ｃ0 + 4Ｃ1 + 4Ｃ2 + 4Ｃ3 + 4Ｃ4

となります。

そこで、一般項Qnを考えると、

Qn = n-1Ｃ0 + n-1Ｃ1 + n-1Ｃ2 + … + n-1Ｃn-1

ですね。

計算は、後日…。

と書いたところで、思い出した。『数学ガール』に「2項定理」って出てたな…。