2以上の自然数$n$を1と2のみの和として表す方法は何通りあるか.
\ \ ただし,\ 和の順序が異なる表し方も同じ表し方とする.
(2)\ \ 2以上の自然数$n$をそれより小さい自然数の和として表す方法は何通りあるか.
\ \ ただし,\ 和の順序が異なるものは別の表し方とする. \\
自然数の分割 \\
(1)\ \ 1と2の和として表す方法が何通りあるかは,\ 何個の2を使って表せるか}に等しい.
n=2のとき & 1通り
n=(4以上の偶数)のとき & n2+1\ 通り
n=(3以上の奇数)のとき & n-1}{2}+1\ 通り
小さい自然数の場合を具体的に書き出すことにより,\ 本質に気付けるかが問われている.
2=1+1 3=2+1=1+1+1 4=2+2=2+1+1=1+1+1+1
5=2+2+1=2+1+1+1=1+1+1+1+1
2の和の残りを1のみの和で表す表し方は1通りしかない.
よって,\ 1と2の和として表す方法は2の個数のみで決まる.
つまりは,\ 2を最大で何個使えるか}を求めればよい.
nを2で割ることになるが,\ 奇数の場合は割り切れないので場合分けする必要が生じる.
nが偶数のとき,\ 最大で\, n2\,個の2が使える.
よって,\ 2を何個使って表すかは,\ 0,\ 1,\ ･･･,\ n2\,の\, n2+1通りある.
ただし,\ n=2のとき1個の「\,2\,」は条件を満たさないので,\ さらなる場合分けの必要が生じる.
nが奇数のとき,\ 最大で\,n-1}{2}\,個の2が使える.\ 例えば,\ n=5のときは\,5-1}{2}=2個である
(2)\ \ $n$の表し方は,\ $n=1+1+･･･+1$の$n-1$個の各$+$を計算するか残すか}で1つ決まる.
すべての$+$を計算する1通りを除く}から,\ 自然数$n$の表し方は $2^{n-1}-1\ (通り)}$
$n$個の自然数の和で表すことは,\ $n$個の○の間に$n-1$本の$|$を入れることに等しい.}
2個の自然数の和で表す方法は $C{n-1}{1}\ (通り)$
3個の自然数の和で表す方法は $C{n-1}{2}\ (通り)$
$\vdots$
$n$個の自然数の和で表す方法は
以下のような非常にうまい考え方が知られている.\ 初見で気付ける人は少ないだろう.
4の表し方は,\ 1の和で表したときの3つの+のそれぞれを計算するか残すかで1つ決まる.}
1つの+につき計算するか残すかの2通りがある}から,\ 4の表し方は2^3\,通りある(重複順列}).
ただし,\ すべての+を計算してしまうと和の形にならない}から,\ この場合を除く必要がある.
初見で思いつくのは,\ 何個の自然数の和になるかで場合分けする方法}だろう(別解).
2個の自然数の和で表すことは,\ x+y=n\ (x≧1,\,y≧1)を満たす整数解を求める}ことに等しい.
このような方程式の整数解の組数は,\ ○と|の並びに対応させて求める}とよいのであった.
例えば,\ x+y=5ならば,\ ○○○|○○と3+2=5が対応する.
5個の○の間に1本の|の入れ方が何通りあるかを考えればよいから,\ C41\,通りと求められる.
二項係数\,C nr\,の和}は二項定理}で求められるが,\ 数II}の範疇なのでここでは簡潔な解説に留める.
二項定理より (a+b)^n=C n0a^n+C n1a^{n-1}b+C n2a^{n-2}b^2+･･･+C{n}{n-1}ab^{n-1}+C nnb^n
C nr\,の和は,\ (1+x)^n\,の二項展開式に適切なxの値を代入すると求まる.
本問は\,C{n-1}{r}\,の和であるから,\ (1+x)^{n-1}\,の二項展開式に適切なxの値を代入する.
本問では2+2+1,\ 2+1+2,\ 1+2+2を別物とみて数えたわけだが,\ これはあまり面白くない.
和の順序が異なるものを同じ表し方と見なすと何通りあるかの方が興味深い.
自然数nを自然数の和として表す方法の総数を分割数}といい,\ p(n)}と表す.
例えば,\ p(5)=7である(分割数p(n)はn自体も1通りと数える).
5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1
このp(n)を一般的に求めるのは大変難しく,\ 学問レベルの話になる.
2011年になってようやく,\ 小野らによってp(n)の有限で代数的な公式が得られた.
