再帰・組み合わせ

質問

新しく再帰という概念を習い始めたのですが、組み合わせを求めるやり方がわかりません
組み合わせの公式通り（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 · ベストアンサー

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

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[個]選ぶ
組み合わせの和と等しい

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

お礼

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

回答No.4

osamuy

http://www.ne.jp/asahi/search-center/internationalrelation/mathWeb/arithmetic/PrmtCmbnBinomialTheorem/PrmtCmbnBinomialThrm.htm#PascalTriangle

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

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

回答No.3

KDASH-XP

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

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

参考URL：

http://d.hatena.ne.jp/ibaza/20080303/1204476552

回答No.1

koko_u_u

>そして何故足してるのかがよくわかりません。
順列、組み合わせ、高校生の頃に習いませんでしたか？