再帰・組み合わせ

新しく再帰という概念を習い始めたのですが、組み合わせを求めるやり方がわかりません
組み合わせの公式通り（nCk　→　n!/k!(n-k)!）、例えば4C2なら答えは6通りになるのはわかるのですが、

public static int combinations(int n, int k){

if(k==n){
return 1;
}else if(k=1){
return n;
}else if(0<k && k<n){

combinations(n-1, k-1) + combinations(n-1, k) ←これで出来るらしいのです

}
}

combinations(n-1, k-1)は意味がわかるのですが、combinations(n-1, k)これが組み合わせの公式にどうあてはまっているのかがわからず、
そして何故足してるのかがよくわかりません。どなたかお解かりになればお願いします

No.2 ベストアンサー 回答者： KDASH-XP 回答日時： 2009/04/11 22:17

こんばんわ。

私も再帰処理とか懐かしいなと思って、ちょっと読みはじめて
不思議に思いました。

combinations(n-1, k-1) + combinations(n-1, k)

強引ですけど
上記式を（nCk　→　n!/k!(n-k)!）にあてはめて、展開すると
もとの式と一致します。
ということは、（nCk　→　n!/k!(n-k)!） から
combinations(n-1, k-1) + combinations(n-1, k)も導き出せるはずなのかなと思いました。

直訳すると「n[個]からk[個]選ぶ」組み合わせは

(n-1)[個]から(k-1)[個]選ぶ、(n-1)[個]からk[個]選ぶ
組み合わせの和と等しい

だと思いますが、なぜこの式なのかは分かりません。
すみません。

この回答へのお礼

みなさんどうもありがとうございました！組み合わせと再帰のアルゴリズムがよくわかっていなかったのでこんがらがってしまいました。
ありがとうございました！

お礼日時：2009/04/12 00:03

No.4 回答者： osamuy 回答日時： 2009/04/11 22:25

http://www.ne.jp/asahi/search-center/internation …

たしかに高校の数学ですね。

実際に動かしてみて、デバッガやprint文出力で挙動を確認してみては。
頭が働かないときは体を動かすのもひとつの手。

No.3 回答者： KDASH-XP 回答日時： 2009/04/11 22:21

同じような記述をネット上で見つけました。

（すみません、私自身が興味半分で調べているので、もう適当です。）

参考URL：http://d.hatena.ne.jp/ibaza/20080303/1204476552

No.1 回答者： koko_u_u 回答日時： 2009/04/11 21:26

>そして何故足してるのかがよくわかりません。

順列、組み合わせ、高校生の頃に習いませんでしたか？