組み合わせ(nCkに関して)

質問

nCkをプログラムで求めるのに、
n-1Ck-1 + n-1Ck (0<k<nの時)
で求めることができるらしいのですが、
この性質がいまいち、良く分からないんです。
どうか、少し詳しく教えてください。
私は大学生なのでそれくらいのレベルでお願いします。

回答No.6

guiter

言葉の説明だと、No3 の yacob さんのようになると思います。
いきなり
　nＣk = n-1Ｃk-1 + n-1Ｃk
と書くよりも
　nＣk = (n-1Ｃk-1)*(1Ｃ1) + (n-1Ｃk)*(1Ｃ0)
と書いたほうが意味をつかみやすいかもしれませんね。

回答No.5

aton

なぜ
nCk = n-1Ck-1 + n-1Ck
となるかについては他の方が書かれているので，私はプログラムについて書きます。
　以下，C-likeな擬似プログラムで記述します。

long combination(int n, int k)

という関数を考えます。実際の処理はこんなふうに記述されます。（適当に書いてるのであんまりきれいなコードではありません。悪しからず）

int combination(int n, int k)
{
　if (n < k) {
　　/// エラー
　　return -1;
　} else if (n == k) {
　　return 1;
　} else {
　　if (k = 1) {
　　　return n;
　　} else { /// 1 < k < n
　　　/// ここで nCk = n-1Ck-1 + n-1Ck を利用
　　　return (combination(n-1, k-1) + combination(n-1, k));
　　}
　}
}

　このように，一つの combination(n,k) を，combination(n-1, k-1) + combination(n-1, k) のように，より引数の小さい2つのcombination関数の結果の和として表すことで，プログラムがコンパクトかつわかりやすくなります。

　なお，たしか nCk = nCn-k だったはずなので，これを利用してやればcombination関数の処理はより高速になるはずです。

お礼

ご返答ありがとうです。
わざわざプログラムまで書いてもらって、、
それで、この内容をみると、どんどん枝状に
別れていって、最終的に"1"を足しているようですが
何故このようになるのでしょうか?
どなたか教えてもらえませんか?

回答No.4

pei-pei

こういうことでしょうか？

仮にｎ＝８，ｋ＝５としてみます。
８個の個体をａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈとして、8Ｃ5を考えてみます。
aを選ぶ場合と、選ばない場合に分けて考えてみると、
まずａを選ぶ場合は、残りのｂ～ｈから４個を選ぶことになるので、7Ｃ4です。
aを選ばない場合は、残りのｂ～ｈから５個を選ぶので、7Ｃ5です。
従って、8Ｃ5＝7Ｃ4＋7Ｃ5　となります。

はたして、答になっているでしょうか？

回答No.3

yacob

No.2で数式による説明がすでになされていますが、言葉で説明すると次のようになります。
n個の中の特定の1個を含むk個の組み合わせは、特定の1個を除いたn-1個からk-1個を選ぶ組み合わせになりますから、その数は、n-1Ck-1　となります。
次に、先に選んだ特定の1個を含まない組み合わせは、n-1個の中からk個を選ぶことになりますから、その数は、n-1Ck　となります。
この2つの場合が、n個のうちからk個を選んだ組み合わせのすべてですから、この2つを足したものが、nCk　となります。
つまり　nCk=n-1Ck-1+n-1Ck となります。
以上がご質問の趣旨に合っているかどうか、わかりませんが、もし違っていたら、お許しください。

お礼

ありがとう御座います。
私が聞きたかった意味がまさにこれです。
あとは、プログラムの内容を理解するだけです。
感謝してます。

回答No.2

rei00

> この性質がいまいち、良く分からないんです。
> どうか、少し詳しく教えてください。
　性質とおっしゃるのが何を指しているかが判らないので，的外れな回答かも知れませんが，nCk = n-1Ck-1 + n-1Ck は簡単に証明できます。

　nCk = n!/k!(n-k)! はご存知ですよね。この関係を使えば，
　n-1Ck-1 + n-1Ck = (n-1)!/(k-1)!(n-k)! + (n-1)!/k!(n-k-1)!

　ここで通分するために，第１項の分母分子に k を，第２項の分母分子に (n-k) をそれぞれ掛けると，
　n-1Ck-1 + n-1Ck = (n-1)!/(k-1)!(n-k)! + (n-1)!/k!(n-k-1)!
　　　　　　　　　= (n-1)!k/k!(n-k)! + (n-1)!(n-k)/k!(n-k)!
　　　　　　　　　= (n-1)!(k+n-k)/k!(n-k)!
　　　　　　　　　= n!/k!(n-k)!
　　　　　　　　　= nCk

　いかがでしょうか。ご質問の意図が，何故この式が出てくるのかにある様でしたら，専門家にお任せします。

補足

スイマセンm(_ _)m 説明不足で、、
つまりですね、どうしていきなり nCk = n-1Ck-1 + n-1Ck
の形がでてくるというか、、どうだからこの形になっているというか
上手く伝えられなくて、くやしいんですが、、、

回答No.1

zerosix

>この性質がいまいち、良く分からないんです。
プログラムについててではないということですよね？

大学生ということで、馬鹿にするなと言われるかもしれませんが、
私はイメージがつかない場合、具体的な数を入れて考えます。
n=8,k=5としてみて、具体的に考えてみてはどうでしょう？
他にも具体的な数を代入してみると、意味が分かるのではないですか？

ちょっと昔のことなので、計算していませんが、
nCk=n-1Ck-1 + n-1Ck (0<k<nの時)
を証明することって、右辺をがりがり計算すればできませんかね？

某大学の数学科卒なので、経験者とさせていただきます。