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

このQ&Aに関連する最新のQ&A

A 回答 (6件)

言葉の説明だと、No3 の yacob さんのようになると思います。


いきなり
 nCk = n-1Ck-1 + n-1Ck
と書くよりも
 nCk = (n-1Ck-1)*(1C1) + (n-1Ck)*(1C0)
と書いたほうが意味をつかみやすいかもしれませんね。
    • good
    • 0

 なぜ


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関数の処理はより高速になるはずです。
    • good
    • 0
この回答へのお礼

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

お礼日時:2001/07/13 15:02

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



仮に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 となります。

はたして、答になっているでしょうか?
    • good
    • 0

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 となります。
以上がご質問の趣旨に合っているかどうか、わかりませんが、もし違っていたら、お許しください。
    • good
    • 0
この回答へのお礼

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

お礼日時:2001/07/13 15:05

 


> この性質がいまいち、良く分からないんです。
> どうか、少し詳しく教えてください。
 性質とおっしゃるのが何を指しているかが判らないので,的外れな回答かも知れませんが,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

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

 

この回答への補足

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

補足日時:2001/07/11 15:19
    • good
    • 0

>この性質がいまいち、良く分からないんです。


プログラムについててではないということですよね?

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

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

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

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q「頭悪いね」「バカだね」 どっちがよりムカつく?

こんにちは、

単純な質問です。

「お前、頭悪いな」

「お前バカだな」

どっちがより言われたらムカつきますか?

Aベストアンサー

どっちもそれなりにムカつきますけど・・・「頭悪いな」かな~

そう言う事を他人に平気で言う奴ほど、バカで頭の悪い人はいないと思いますけど・・・ね?
我がふりなおせよ~ってな感じです。

でもやっぱり傷つくな~否定はしないけど(苦笑)

QnCk=(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
を全部書きだして、通分して足しても何もなりませんでした……

すいませんが、ご存じの方がいらっしゃいましたらご教授ください。
よろしくお願いします。

Aベストアンサー

二項定理 (1+x)^n = (nC0) + (nC1)x + (nC2)x^2 + … + (nCn)x^n

を n について漸化しましょう。(1+x)^n = (1+x)・(1+x)^(n-1) より、

(nC0) + (nC1)x + … + (nCn)x^n = (1+x){ ((n-1)C0) + ((n-1)C1)x + … + ((n-1)C(n-1))x^(n-1) }.

両辺の x^k 項を比較すれば、(nCk)x^k = 1・((n-1)Ck)x^k + x・((n-1)C(k-1))x^(k-1).

すなわち nCk = (n-1)Ck + (n-1)C(k-1).



趣味的な話ですが、私は、nCk = n!/{k!(n-k)!} を定義とするよりも、

二項定理のほうを nCk の定義として、逆に n!/{k!(n-k)!} は導出する

立場のほうが好きだなあ。「二項係数」って、そういう名前でしょ。

Q仕事が遅い、頭悪い、力仕事できない 不器用すぎるこんなパートメリットありますか?

仕事が遅い、頭悪い、力仕事できない
不器用すぎるこんなパートメリットありますか?

Aベストアンサー

仕事が早い、頭が良い、力仕事もできる
器用すぎるこんなパートに比べたら、見劣りしますが、
居ないよりはずいぶんましだと思いますよ。

Qこうゆう考えの人って頭悪いと思わないですか?

こうゆう考えの人って頭悪いと思わないですか?
CMとかで嫌いなタレント出てるからとかむかつくからという理由で商品買わない人
僕には理解出来ないですが何か?
商品なんて関係ないしあれですか?坊主にくけりゃ袈裟憎いって?
でも向こうもそうゆう考えもつ人にはかってもらいたくないからいいかなと思うけど

Aベストアンサー

なるほど、そういう考えもできますか!

広告というのは、その商品なりサービスが、一番いい方法で訴求できて、消費者に認知・浸透してアクションを起こしてもらうことが、最終的な目的ですよね。

そしてそのためには、(関係者のしがらみはともかくとして)それにマッチする、イメージを伝えられるに相応しいタレントを起用するのが普通です。
ですから、広告でそのタレントが出ることは、その商品なりサービスのイメージを背負っているということになります。

なので、質問者さまがおっしゃっている「タレントが嫌いだから商品を買わない」という人が出てきても、何らおかしくありません。
別に頭が悪いわけではありません。
よく、不祥事を起こしたタレントが出た時、そのタレントのCMを一斉に引き上げますね。それによって商品イメージが下がることを恐れてのことです。

Q3/(n+2)(n+5)= 1/3 {<1/(n+2)>-<1/(n+5)>} ???

{1/(n+2)}-{1/(n+5)}=3/(n+2)(n+5)…(1)です。更に
1/3 {<1/(n+2)>-<1/(n+5)>}…(2)
にと変形できるそうです。
読んでいる本に、(1)の分子の3を1にする為に上の変形が紹介されていたのですが、

(1)と(2)は同じ数値、大きさになるのでしょうか? 
分子と分母で数字が同じでも、分子を1にして元々の数字で割ってしまっては(分母に元の数字を)、違う大きさになると思うのですが…
2/1と1/2は違いますし…

Aベストアンサー

A-B=3Cだから、C=(1/3)(A-B)だ、といっているのです。

1/(n+2)-1/(n+5)=3{1/(n+2)(n+5)}だから
1/(n+2)(n+5)=(1/3){1/(n+2)-1/(n+5)}になりますよということ。
(2)の方の式に等号がありませんが、左辺(あるいは右辺)に
くるべきものをいっしょに考えてください。

Qわざわざナイフからフォークに利き手を持ち替えないと食事出来ない人って、頭悪いの?躾がなってないの?

わざわざナイフからフォークに利き手を持ち替えないと食事出来ない人って、頭悪いの?躾がなってないの?



「俺、右利きだから」とかいう理由でフォークをいちいち右手に持ち替えないと食べられない育ちの悪いクソとは食事したくない。



右利きならナイフが右手、フォークが左手だろ。子どもでも知ってるわ。

それが出来ない成人とか脳腐ってるでしょ?


こんな腐った食事の仕方してる人って親に食事の仕方すら教わってないからこんな気持ち悪いことするんでしょうか?

それとも教わっても理解できないくらいに頭が悪いからなのか?

Aベストアンサー

私はオジサンです。
両親は2人とも地方出身です。イギリスではありません。日本です。
ナイフとフォークを使う食事なんて、した事がないし、必要もなく育ちました。
質問者様とは生きてる世界が違うようですね(笑)。
それとも、わざと炎上させるように挑発的に書いているのでしょうか?
質問者様は、カップ麺って、食べた事ないんでしょうね。
質問者様は、1日の食事代1000円未満なんて、経験ないんでしょうね。
世の中、あなたのような人ばかりではないのですよ。
自身の価値観だけで、相手を否定するのは、テーブルマナーより酷いマナーですよ。

Q1/2*3(n+1)(n+2)-2(n+2)-2(n+1)/2(n+1)(n+2)=???

(1)1/2*{3(n+1)(n+2)-2(n+2)-2(n+1)}/2(n+1)(n+2)=
(2)(3n^2+5n)/4(n+1)(n+2) なのだそうですが…
自分で紙に書いて計算しても(2)になりません。

(2)になるまでを詳しく書いてください。

3(n+1)(n+2)-2(n+1)(n+2)として計算したのですが…

Aベストアンサー

{3(n+1)(n+2)-2(n+2)-2(n+1)}を整理してみます。

{3(n+1)(n+2)-2(n+2)-2(n+1)}
 =3(n^2+3n+2)-2n-4-2n-2
 =3n^2+9n+6-4n-6
 =3n^2+5n

1/2*{A}/2(B)={A}/4(B) ですから、

1/2*{3(n+1)(n+2)-2(n+2)-2(n+1)}/2(n+1)(n+2)
 ={3(n+1)(n+2)-2(n+2)-2(n+1)}/4(n+1)(n+2)
 =(3n^2+5n)/4(n+1)(n+2)

>3(n+1)(n+2)-2(n+1)(n+2)として計算したのですが…

-2(n+2)-2(n+1)=-2(n+1)(n+2)とされたんですね。
-2a-2b=-2(a+b)ですから(逆に展開してみてください)
-2(n+2)-2(n+1)=-2{(n+2)+(n+1)}です。

Q30代なかばで派遣してます。頭悪いし、毎日サービス残業してもいいんだけど、あまり夜遅くまですると寝坊

30代なかばで派遣してます。頭悪いし、毎日サービス残業してもいいんだけど、あまり夜遅くまですると寝坊してしまうし、このまま派遣続けようかと考えてます。こんな人生もありですかねぇ?子供好きだけど、子孫も残さないつもりです。

Aベストアンサー

将来的な計画などを考えても、自分で良しと思えるならありだと思います。

ただ、生涯賃金にして二倍以上の差がつくと言われている非正規と正規では
老後の生活や、中年を過ぎる辺りからの生活に差が出てきます。
周囲との比較というのは自分で気を向ける以上に気になるものです。

また、実生活面でも万が一のことがあった場合など
様々な場面で不利な状況に立たされる可能性も考えるべきです。

そういった点から、生涯派遣労働というのは
今の社会、制度の状態ではお勧めしたいとは思えません。
ただ、正規労働よりもストレスが少ない場合があることも確かです。
ライフスタイルやワークスタイルは個人が選んでよいものですから
そういったリスクを考えてもなお、自分に合っている
もしくは、そういったスタイルが良いと思うのであれば
一つの生き方だと思います。

Q高1数Aの順列の公式の意味がわかりません。 nPr=n(n-1)(n-2)...(n-r+1)=n!

高1数Aの順列の公式の意味がわかりません。
nPr=n(n-1)(n-2)...(n-r+1)=n!/(n-r)!
のn-r+1の意味と、n!/(n-r)の意味を教えていただきたいです。

Aベストアンサー

一番最初の n は、(nー0) で第一項で、第二項は、(nー1)ですから、第 r 項なら (nーr+1)
になりますね!つまり、nー0と0から始まっていて、1からではないからですね!
n ❗/ (nーr)❗は、わかりましたか?
n❗=n(nー1)(nー2)…(nーr+1)(nーr)(nーrー1)(nーrー2)…
(nーr)❗=(nーr)(nーrー1)(nーrー2)…
であり、
n❗で、(nーr)(nーrー1)(nーrー2)…つまり、(nーr)❗が重複しているので、
割ると、
n(nー1)(nー2)…(nーr+1)(nーr)(nーrー1)は、n❗/(nーr)❗になりますね!


人気Q&Aランキング

おすすめ情報