質問＜１４９１＞２００３／１１／１６
from=jack
「自然数の分割数について」

P(n,k)=P(n-1,k-1)+P(n-k,k)
はどうやって証明すればよいでしょうか？

お便り２００３／１２／９
from=下野哲史

証明ですか。。。
あまり整数論は詳しくはないので、証明は勘弁して下さい。
分割数という言葉も恥ずかしながら今回初めて知りました。
まず、調べたところ P(n,r) とは 自然数 n を r 個の自然数に分割する
分け方の場合の数である。ただし、この分け方は順序は問わない。
例えば、P(5,3) は 5 を ３個に分ける方法、1+1+3 , 1+2+2 の ２通りより
　　　　　　 P(5,3)=2
　　　　P(7,4) は 7 を ４個に分ける方法、1+1+1+4 , 1+1+2+3 , 1+2+2+2
　　　　　　 の３通りより P(7,4)=3
　　　　P(8,3) は、1+1+6 ,1+2+5 , 1+3+4 , 2+2+4 , 2+3+3 より
　　　　　　 P(8,3)=5 である。
この P(8,3) に注目してみる。
1 が入った分け方 1+1+6 , 1+2+5 , 1+3+4 １をとると、1+6 , 2+5 , 3+4 となり、
これは P(7,2) である。
1 が入っていない分け方 2+2+4 , 2+3+3 は、３つ全部から１引くと、
1+1+3 , 1+2+2 となり、これは P(5,3) である。
よって、P(8,3)=P(7,2)+P(5,3)

同様にして考えればよいのでは？
P(n,r) の分け方を a1 + a2 + a3 + … + ar と表す。
a1, …, ar の中で、1を含むものが ak であれば、それを取り除いた 
a1 + a2+ … +a(k-1) +a(k+1) + … + ar は  P(n-1,r-1) と同じである。
a1, …, ar の中に１が含まれないならば、(a1-1)+(a2-1)+…(ar-1)=n-r 
より分割方法は P(n-r,r) と同じである。
よって、P(n,r)=P(n-1,r-1)+P(n-r,r) と考えられる。
 
自分としても大変勉強になりました。