OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
締切り
済み

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

  • 暇なときにでも
  • 質問No.102681
  • 閲覧数980
  • ありがとう数10
  • 気になる数0
  • 回答数6
  • コメント数0

お礼率 57% (8/14)

nCkをプログラムで求めるのに、
n-1Ck-1 + n-1Ck (0<k<nの時)
で求めることができるらしいのですが、
この性質がいまいち、良く分からないんです。
どうか、少し詳しく教えてください。
私は大学生なのでそれくらいのレベルでお願いします。
通報する
  • 回答数6
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

回答 (全6件)

  • 回答No.2
レベル14

ベストアンサー率 50% (1133/2260)

  > この性質がいまいち、良く分からないんです。 > どうか、少し詳しく教えてください。  性質とおっしゃるのが何を指しているかが判らないので,的外れな回答かも知れませんが,nCk = n-1Ck-1 + n-1Ck は簡単に証明できます。  nCk = n!/k!(n-k)! はご存知ですよね。この関係を使えば,  n-1Ck-1 + n-1Ck = (n-1)!/(k-1) ...続きを読む
 
> この性質がいまいち、良く分からないんです。
> どうか、少し詳しく教えてください。
 性質とおっしゃるのが何を指しているかが判らないので,的外れな回答かも知れませんが,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)!

 ここで通分するために,第1項の分母分子に k を,第2項の分母分子に (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

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

 
補足コメント
ma-kunn

お礼率 57% (8/14)

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


  • 回答No.1
レベル10

ベストアンサー率 31% (47/149)

>この性質がいまいち、良く分からないんです。 プログラムについててではないということですよね? 大学生ということで、馬鹿にするなと言われるかもしれませんが、 私はイメージがつかない場合、具体的な数を入れて考えます。 n=8,k=5としてみて、具体的に考えてみてはどうでしょう? 他にも具体的な数を代入してみると、意味が分かるのではないですか? ちょっと昔のことなので、計算していま ...続きを読む
>この性質がいまいち、良く分からないんです。
プログラムについててではないということですよね?

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

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

某大学の数学科卒なので、経験者とさせていただきます。
  • 回答No.3
レベル9

ベストアンサー率 40% (25/62)

No.2で数式による説明がすでになされていますが、言葉で説明すると次のようになります。 n個の中の特定の1個を含むk個の組み合わせは、特定の1個を除いたn-1個からk-1個を選ぶ組み合わせになりますから、その数は、n-1Ck-1 となります。 次に、先に選んだ特定の1個を含まない組み合わせは、n-1個の中からk個を選ぶことになりますから、その数は、n-1Ck となります。 この2つの場合が、n個のう ...続きを読む
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 となります。
以上がご質問の趣旨に合っているかどうか、わかりませんが、もし違っていたら、お許しください。
お礼コメント
ma-kunn

お礼率 57% (8/14)

ありがとう御座います。
私が聞きたかった意味がまさにこれです。
あとは、プログラムの内容を理解するだけです。
感謝してます。
投稿日時 - 2001-07-13 15:05:12
  • 回答No.4
レベル10

ベストアンサー率 23% (20/86)

こういうことでしょうか? 仮にn=8,k=5としてみます。 8個の個体をa,b,c,d,e,f,g,hとして、8C5を考えてみます。 aを選ぶ場合と、選ばない場合に分けて考えてみると、 まずaを選ぶ場合は、残りのb~hから4個を選ぶことになるので、7C4です。 aを選ばない場合は、残りのb~hから5個を選ぶので、7C5です。 従って、8C5=7C4+7C5 となります。 はたして、答 ...続きを読む
こういうことでしょうか?

仮にn=8,k=5としてみます。
8個の個体をa,b,c,d,e,f,g,hとして、8C5を考えてみます。
aを選ぶ場合と、選ばない場合に分けて考えてみると、
まずaを選ぶ場合は、残りのb~hから4個を選ぶことになるので、7C4です。
aを選ばない場合は、残りのb~hから5個を選ぶので、7C5です。
従って、8C5=7C4+7C5 となります。

はたして、答になっているでしょうか?
  • 回答No.5
レベル11

ベストアンサー率 47% (160/334)

 なぜ nCk = n-1Ck-1 + n-1Ck となるかについては他の方が書かれているので,私はプログラムについて書きます。  以下,C-likeな擬似プログラムで記述します。 long combination(int n, int k) という関数を考えます。実際の処理はこんなふうに記述されます。(適当に書いてるのであんまりきれいなコードではありません。悪しからず) ...続きを読む
 なぜ
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関数の処理はより高速になるはずです。
お礼コメント
ma-kunn

お礼率 57% (8/14)

ご返答ありがとうです。
わざわざプログラムまで書いてもらって、、
それで、この内容をみると、どんどん枝状に
別れていって、最終的に"1"を足しているようですが
何故このようになるのでしょうか?
どなたか教えてもらえませんか?
投稿日時 - 2001-07-13 15:02:22
  • 回答No.6
レベル10

ベストアンサー率 51% (86/168)

言葉の説明だと、No3 の yacob さんのようになると思います。 いきなり  nCk = n-1Ck-1 + n-1Ck と書くよりも  nCk = (n-1Ck-1)*(1C1) + (n-1Ck)*(1C0) と書いたほうが意味をつかみやすいかもしれませんね。
言葉の説明だと、No3 の yacob さんのようになると思います。
いきなり
 nCk = n-1Ck-1 + n-1Ck
と書くよりも
 nCk = (n-1Ck-1)*(1C1) + (n-1Ck)*(1C0)
と書いたほうが意味をつかみやすいかもしれませんね。
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ