- ベストアンサー
組み合わせの公式
- みんなの回答 (5)
- 専門家の回答
質問者が選んだベストアンサー
左辺=n人からk人の「グループ」を作り、さらにグループの「リーダー」を決めるときの場合の数。 右辺=n人から「リーダー」を一人選び、残りのn-1人からk-1人を選び、合計k人の「グループ」をつくるときの場合の数。 以上
その他の回答 (4)
- paatje
- ベストアンサー率51% (23/45)
私も、それほど意味があるとは思いませんが…。 k・nCk = nCk・k ですから、左辺は、 n個の中から、k個選んで、その中から、一つ選ぶ組み合わせ ですよね。 結果、1個の特別な要素と、(k-1)個の要素からなる集合(順番はどうでもいい)とが得られます。 これを、手順を変えて、 n個の中から、まず特別な要素を1個選び、 残った(n-1)個の中から、(k-1)個の要素からなる集合を選ぶ、 ようにしたのが、 右辺です。 こんなんでよろしいでしょうか?
補足
お返事ありがとうございます。 >結果、1個の特別な要素と、(k-1)個の要素からなる集合(順番はどうでもいい)とが得られます。 すいませんyacob様への質問と重なるですが、右辺がよくわかりません。 それと、これは「Σ(k=0→n)k・nCk」を求めよという問題にちなんで出てきたものです。
- yacob
- ベストアンサー率40% (25/62)
言葉による説明が出ていないようですので、遅ればせながら、考えを申し上げます。説明がくどくなります。ご理解いただけるとよいのですが。 n個のうちから、k個を選ぶ組み合わせについて、k個のうちの特定番目(以下、特定席と書きます。一番初めでも、終わりでも、途中でもよいのですが。)に来るものによって、k個のすべてが同じでも、別なものとするといった組み合わせ方を考えます。 たとえば、A,B,C,Dの4つについて、3つを選ぶ組み合わせでは、普通は、ABCはBCA、BAC、CAB、...と同じで、これらは1個としかカウントできませんが、この場合は、特定席を一番初めとして、ABCは、BCA、BAC、CAB、…は別物とするわけです。ただし、特定席のA以外は順序に無関係ですから、ABC、ACBは1つとなります。 n個のうちから、k個を選ぶ組み合わせについて、これを考えると、 1.・特定席の1個を、n個のうちから選ぶnの場合のそれぞれのついて、k個の残りのk-1個を、n個の残りn-1個から選ぶ組み合わせの数, n-1Ck-1 だけありますから、総数は、n*n-1Ck-1 となります。 2・次に、別にこれを考えますと、n個のうちから、k個を選ぶ単純な組み合わせは、nCk の組数がありますが、その1組ごとについて、特定席にk個のうちの1つを入れる組み合わせは、k個ありますから、総数は、k*nCk であります。 上記の1、2は、答えを得る筋道が違っただけですから、同じであります。つまり、与式が証明されたわけです。
補足
お返事ありがとうございます。 >1.・特定席の1個を、n個のうちから選ぶnの場合のそれぞれのついて、k個の残りのk-1個を、n個の残りn-1個から選ぶ組み合わせの数, n-1Ck-1 だけありますから、総数は、n*n-1Ck-1 となります。 すいません。ここがわかりません。特等席を1個選ぶには誰を特等席にするかのn通りしかないように思われるのですが、n-1Ck-1 はなにを計算しているのかよくわかりません。
日本語でということですが・・・ 私が考えるには、 この公式じたいにはあまり意味がなく(意味が無くもないかもしれませんが・・・) nCk とn-1Ck-1の間の関係式というか、変形しただけだと思います。 つまり nCk = n /k・n-1Ck-1 は分かりますでしょうか? nCk = n ・(n-1)・・・(n-K+1)/k・(k-1)・・・・2・1 =n/k・(n-1)・・・(n-k+1)/(k-1)・・・・2・1 =n /k・n-1Ck-1 あとは、両辺にKを掛けただけです。 私の結論は、 無理やりこじつけて、k ・nCk = n ・n-1Ck-1 に意味をつけられるかもしれませんが、ただ変形しただけだと思います。
お礼
お返事ありがとうございます。ただの変形だったのですね。これなら自分でもすぐ作れそうです。ありがとうございます。
- 128yen
- ベストアンサー率44% (107/243)
左辺のnCkは公式に当てはめて(教科書に載っています) nCk =n・(n-1)・(n-2)・・・・{n-(k-1)}/k! =n・(n-1)・(n-2)・・・・(n-k+1)/k! ここでk!とは k・(k-1)・(k-2)・・・2・1なので式を変形してk!=k・(k-1)!と出来ます。 よって左辺は =k・n・(n-1)・(n-2)・・・・(n-k+1)/k・(k-1)! =n・(n-1)・(n-2)・・・・(n-k+1)/(k-1)! 右辺のn-1Ck-1を同様に公式に当てはめると n-1Ck-1 =(n-1)・{(n-1)-1}・・・・[(n-1)-{(k-1)-1}]/(k-1)! =(n-1)・(n-2)・・・・(n-k+1)/(k-1)! となります。 よって右辺は =n・(n-1)・(n-2)・・・・(n-k+1)/(k-1)! 左辺と右辺は同じなので等号が成立するわけです。
お礼
お返事どうもありがとうございます。式の変形もわからなかったので、解説していだだけてとても参考になりました。
関連するQ&A
- 組み合わせ(nCkに関して)
nCkをプログラムで求めるのに、 n-1Ck-1 + n-1Ck (0<k<nの時) で求めることができるらしいのですが、 この性質がいまいち、良く分からないんです。 どうか、少し詳しく教えてください。 私は大学生なのでそれくらいのレベルでお願いします。
- 締切済み
- 数学・算数
- 高校数学の数列の和の計算 4-7再質問
高校数学の数列の和の計算 4-7 次の和を計算せよ (1)Σ[k=1→n]k・nCk (2)Σ[k=1→n]k^2・nCk 解説は(1)はK・nCk=n・n-1Ck-1となっていてこの式の意味が 左辺の意味ですがn人からk人を選んでそのk人から一人のリーダーを選ぶ場合の数で右辺はリーダーを一人決めて、残りのn-1人からk-1人を選ぶという事ですか?良く分かりません (2)は(1)のK・nCk=n・n-1Ck-1を使って Σ[k=1→n]k^2・nCk=nΣ[k=1→n]k・n-1Ck-1(1) =nΣ[k=1→n]{(k-1)・n-1Ck-1}+n-1Ck-1}(2) =n[Σ[k=2→n]{(k-1)・n-1Ck-1}+Σ[k=1→n]n-1Ck-1](3) =n[(n-1)Σ[k=2→n]{(n-2)・n-1Ck-2}+Σ[k=1→n]n-1Ck-1](4) =n(n-1)・2^(n-2)+n・2^(n-1)(5) =n(n+1)・2^(n-2)(6) とあるのですが(3)から(4)の変形をどうやったのか分かりません
- ベストアンサー
- 数学・算数
- 高校数学の数列の和の計算 4-7
次の和を計算せよ (1)Σ[k=1→n]k・nCk (2)Σ[k=1→n]k^2・nCk 解説はK・nCk=n・n-1Ck-1となっていてこの式の意味が左辺がn人からk人を選び、そのk人から1人のリーダーを選ぶという場合の数で右辺はn人から1人のリーダーを選んでからk人の組をつくるという場合の数で一致するとあるのですが、左辺は分かりますが右辺の意味ですが1人のリーダを選んだ後n-1任からk組作るのだったらn・n-1Ckじゃないんですか? (2)は(1)のK・nCk=n・n-1Ck-1を使って Σ[k=1→n]k^2・nCk=nΣ[k=1→n]k・n-1Ck-1(1) =nΣ[k=1→n]{(k-1)・n-1Ck-1}+n-1Ck-1}(2) =n[Σ[k=2→n]{(k-1)・n-1Ck-1}+Σ[k=1→n]n-1Ck-1](3) =n[(n-1)Σ[k=2→n]{(n-2)・n-1Ck-2}+Σ[k=1→n]n-1Ck-1](4) =n(n-1)・2^(n-2)+n・2^(n-1)(5) =n(n+1)・2^(n-2)(6)とあるのですが(1)から(2)、(2)から(3)、(3)から(4)の変形をどうやったのか分かりません
- ベストアンサー
- 数学・算数
- 再帰・組み合わせ
新しく再帰という概念を習い始めたのですが、組み合わせを求めるやり方がわかりません 組み合わせの公式通り(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)これが組み合わせの公式にどうあてはまっているのかがわからず、 そして何故足してるのかがよくわかりません。どなたかお解かりになればお願いします
- ベストアンサー
- Java
- C言語での組み合わせの問題について
(環境はmacで, gcc 4.0.1を用いています) #include <stdio.h> main(void) { int n, k, nck; printf("n = "); scanf("%d", &n); printf(" k nCk\n"); k = 0; nck = 1; printf("%12d%12d\n", k, nck); for(k=1; k <= n; k++) { nck = nck * (n-k+1)/k; printf("%12d%12d\n", k, nck); } } とした場合, 入力した値n=29までは正しい答えが得られるのですが n=30以降では途中から答えが狂い始めます. この現象はなぜ起こるのでしょうか?
- ベストアンサー
- C・C++・C#
- ライプニッツの公式を使った問題
y=x^2・e^-3x のn階導関数をライプニッツの公式をつかって求める問題についてなのですが、 ライプニッツの公式の[n]Σ[r=0]nCk*f^(n-k)*g^(k)を使って、解答は y^(n)=(-3)^n-2{9x^2-6nx+n(n-1)}e^-3xとなります。 ですがこれってk=0,1,2までしか足していません。なぜk=0,1,2までなのでしょうか?k=0,1 若しくはk=0,1,2,3まで足してしまっては不正解ですか? それともキリがないからたまたま2までで区切っただけでしょうか? kをいくらまで増やして足せばいいかわかりません。 ご教授お願いします。
- ベストアンサー
- 数学・算数
- nCk=(n-1)C(k-1)+(n-1)Ck証明
nCk=(n-1)C(k-1)+(n-1)Ck の証明問題なのですが、やり方が全くわかりません。 nCk (n-1)C(k-1) (n-1)Ck を全部書きだして、通分して足しても何もなりませんでした…… すいませんが、ご存じの方がいらっしゃいましたらご教授ください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
お礼
大変よくわかりました。ありがとうございました。