09/01/12 11:54:35
>>721
二つ目以降の数字についてはすでに使用した数字以下の数字を使うことで
順列を並べ替えたものを除外しています。そのために引数 maximum を使ってます
例） n=4 のとき
4 採用
3 1 採用
1 3 除外
2 2 採用
2 1 1 採用
1 2 1 除外
1 1 2 除外
1 1 1 1 採用
今、huga という関数が自然数 n および maximum を満たす
すべての組み合わせの数を数え上げることができると＊仮定＊します
ある数 i (1≦i≦n かつ i≦maximum) を使用すると決定したときの
組み合わせ数は huga(n-i, min(i, maximum)) で求まります（仮定より）
n=4 の時
4 0 → 1通り (これが else ret++;)
3 1 → huga(1, 1) 通り
2 2 → huga(2, 2) 通り
1 3 → huga(3, 1) 通り
ということで n=4 の時の総組み合わせ数は
1 + huga(1, 1) + huga(2, 2) + huga(3, 1)
になります
仮定を証明するのは自分でどうぞ