二項係数

二項係数nCkについて
nCi=nCj (1≦i<j≦n)
のとき i+j を求めよ。

教えて下さい。

No.13 ベストアンサー 回答者： masterkoto 回答日時： 2021/05/25 17:33

＃２回答者です

ちょっと雑すぎでしたでしょうか？

n-i=mとおいたのは貴方に理解してもらおうと思ったためです
こんな置き換えをせずとも

nCi=n!/{i!・(n-i)!}
=n!/{(n-i)!・i!}
=nC(n-i)…①
ですが、これだとあなたに分からないかもと懸念したのです
（ちなみに①はほぼ常識ですし、組み合わせの計算をいくつかこなした人なら自然と気が付くことです）

ゆえに
nCi=nCj ならば
j=i の可能性もあるし
①との比較で
nCi
=nC(n-i)
=nCjより
j=n-iの可能性もあります
ただし、題意から　i<jなんで今回は前者除外です

で、問題になるのがこの2つ以外にjが他の数値を取る可能性です

nC1=n=n/1
nC2=n(n-1)/2!=(n/1)・{(n-1)/2}
nC3=n(n-1)(n-2)/3!=(n/1)・{(n-1)/2}・{(n-2)/3}
この要領で、n/1の後に新たな掛け算が次々に加わっていくので
しばらくは　nの右の数字が大きくなるほど　nCrの値も単調に大きくなることがわかりますよね。
そして、①式より　nC1=nC[n-1]
nC2=nC[n-2]
nC3=nC[n-3]
ですから、
nC[n-1]
nC[n-2]
nC[n-3]・・・もこの順に単調に増加です
ただし、　n-3<n-2<n-1ですから
Cの右に続く数字を１から順番に並べれば
nC1<nC2<nC3<・・・>nC[n-3]>nC[n-2]>nC[n-3]…②
です
ここまではいいでしょうか？
②はnC1などのその数値を標高にたとえれば
左端同士のnC1とnC[n-3]が等しい標高で
左端から2番目どうしnC2とnC[n-2]　も等しく
・・・
中央に向かうほど高くなる左右対称な山という事ができます
左右対称なんで等しい標高は左右に1対づつです
（ただし場合によっては最高点の中央　nC[n/2]だけはペアを持たない可能性もあります）
ということは、nCi=nCjなら
j=iか　j=n-iに限られますよね！
ゆえに、この問題では
nCi
=nC(n-i)
=nCjより
j=n-iの可能性だけに限定されて
i+j=nなのです
　
これを踏まえて、正確な記述の答案を考えて見てくださいませ

この回答へのお礼

論理があやふやかもしれないなどと疑惑の目を向けて失礼しました…。
こういう解説が知りたかったです…！！ありがとうございました。

お礼日時：2021/05/26 20:14

No.17 回答者： 大地のしもべ 回答日時： 2021/05/26 13:11

ジレンマの使い方が参考になりました。

ガウスの補題の証明と同じ匂いがしたのでなかなか書けなかったところです。

この回答へのお礼

回答していただきありがとうございました。

お礼日時：2021/05/26 20:17

No.16 回答者： stomachman 回答日時： 2021/05/26 11:06

補足なさったことを総括すると：

n≧1のとき
　　∀i∀j( (n≧i≧0 ∧ n≧j≧0) ⇒ ( nCj=nCi ⇒ (i=j ∨ i=n-j) ) )
を言いたい。これは言い換えれば、
　　P(n): ∀j( n≧j≧0 ⇒ nCj=nC(n-j) )
　　Q(n): ∀i∀j( (n≧i≧0 ∧ n≧j≧0 ∧ nCj= Ci) ⇒ (i=j ∨ i=n-j) )
とするとき
　　∀n( n≧1 ⇒ (P(n)∧Q(n)) )
ということだが、ここで
　　∀n( n≧1 ⇒ P(n) )
はすでに証明済みだとして、
　　∀n( n≧1 ⇒ Q(n) )
を証明したい、というのがご質問の趣旨ってことでしょう。

　　R(n): ∀j( 1≦j＜n/2 ⇒ nCj＜nC(j+1) )
とすると
　　∀n( n≧1 ⇒ (R(n)⇒ Q(n)) )
は明らかなので、
　　∀n( n≧1 ⇒ R(n) )
を証明すれば十分である。この証明には、例えばcombinationの性質
　　∀n∀j ((n≧2 ∧ n-1≧j≧1) ⇒ (nCj = (n-1)C(j-1) + (n-1)Cj) …(1)
を使ってnに関する数学的帰納法を適用するのが素直じゃないかな。実際やってみると：

●n=1のとき：
　1≦j＜n/2 を満たすjはないから、R(1)は真。

● n≧2のとき：
　R(n-1): ∀j( 1≦j＜(n-1)/2 ⇒ (n-1)Cj＜(n-1)C(j+1) )を仮定して、R(n)、すなわち、「n≧2, 1≦j＜(n-1)/2 のときに
　　nCj＜nC(j+1)
であること」を証明する。
　n≧2なので、
　　∀k ( 1≦k＜(n-1)/2 ⇒ n-1≧k≧1 )
だから1≦j＜(n-1)/2 のとき、(1)により
　　nCj = (n-1)C(j-1) + (n-1)Cj
　　nC(j+1) = (n-1)Cj + (n-1)C(j+1)
である。従って
　　nC(j+1) - nCj = (n-1)Cj + (n-1)C(j+1) - ((n-1)C(j-1) + (n-1)Cj ))
　　= (n-1)C(j+1) - (n-1)C(j-1) …(2)
ここでジレンマを使う。すなわち
　　 j+1＜(n-1)/2 ∨ j+1≧(n-1)/2
なのだから：
　　Case1. j+1＜(n-1)/2の場合
　　　仮定R(n-1)から
　　　　　(n-1)C(j+1)＞ (n-1)Cj＞ (n-1)C(j-1)
　　　なので(2)は正であり、だから
　　　　　nC(j+1)＞ nCj
　　Case2. j+1≧(n-1)/2の場合
　　　　　j ＜(n-1)/2 ≦ j+1
　　　なので、P(n-1)により
　　　　　(n-1)Cj = (n-1)C(j+1)
　　　である。仮定R(n-1)から
　　　　　(n-1)Cj＞ (n-1)C(j-1)
　　　なので(2)は正であり、だから
　　　　　nC(j+1)＞ nCj
Q.E.D.

この回答へのお礼

ありがとうございます。
しかしこの書き方では私には難しすぎました…。

お礼日時：2021/05/26 20:16

No.15 回答者： 大地のしもべ 回答日時： 2021/05/25 19:31

階乗の公式から厳密に示そうとすると難しい部分があります。

階乗の公式に適当に数を入れて調べたりすればn=i＋j という候補が見つかりそれ以外無いのもほぼ自明です。これが唯一の解であることも条件式の等号などからほぼ自明ですがきちんというには二項係数が上がって下がる値の取り方をすることに言及するしかないと思います。手を動かして計算していればほぼ自明なことなので論理的に突っ込む所ではない。厳密に示したかったら他の表示式でやってみるとか、とにかく自分で工夫してみないと数学はダメです。

この回答へのお礼

そうですね…。
自分で工夫してもどうにもならない限界があったので質問させていただいた…という感じでしょうか…。

お礼日時：2021/05/26 20:15

No.14 回答者： masterkoto 回答日時： 2021/05/25 17:39

#13訂正

不等式②などは誤りでした
正しくは

「nC1<nC2<nC3<・・・>nC[n-3]>nC[n-2]>nC[n-1]…②
です
ここまではいいでしょうか？
②はnC1などのその数値を標高にたとえれば
端同士のnC1とnC[n-1]が等しい標高で
端から2番目どうしnC2とnC[n-2]　も等しく・・・」

となります・申し訳ない。

この回答へのお礼

ありがとうございます。

お礼日時：2021/05/26 20:14

No.12 回答者： 大地のしもべ 回答日時： 2021/05/25 16:32

n個の文字の単純下降列があり、最大項がnで最小項が1ならばそれはnの階乗しか考えられないということです。

iとjに大小関係があるので接続が成り立っていました。

この回答へのお礼

nの階乗しか考えられない、その根拠を知りたい…というところでしょうか…。

お礼日時：2021/05/26 20:11

No.11 回答者： 大地のしもべ 回答日時： 2021/05/25 16:28

n(n-1)(n-2)…(k +1)/(n-k)(n-k -1)…1

=n(n-1)(n-2)…(n-k +1）/k! です。
nCi=nCjより
n(n-1)…(i +1)/(n-i)!=n(n-1)…(n-j＋1)/j! です。
分母を払うと
n(n-1)…(i＋1)j!=n(n-1)…(n-j＋1)(n-i)! です。

ここまで書きましたが、iとjの大小関係をミスしたので逆だと思ってください。

それぞれの下降積がn個で構成されていることが分かるまで積の数について考察したら大丈夫です。左辺のj＋1とiの間に不足している項があることがi≠jの条件が効いてる箇所でした。

これ以上煩雑な文字入力に耐えられないのでこれで勘弁して下さい。

この回答へのお礼

ちょっとこれだけではよくわかりませんでした…。

お礼日時：2021/05/26 20:11

No.10 回答者： 大地のしもべ 回答日時： 2021/05/25 15:39

nCk=n…（k＋1）/（n-k）…1とも書けますよね？

この回答へのお礼

そうですね…。
n(n-1)(n-2)…(i+1)/(n-i)(n-i-1)(n-i-2)…1
n(n-1)(n-2)…(j+1)/(n-j)(n-j-1)(n-j-2)…1
と書けそうです。

こうしてどうするのでしょう？

お礼日時：2021/05/25 16:10

No.9 回答者： 大地のしもべ 回答日時： 2021/05/25 15:31

n（n-1）…（n-i＋1）（n-j）（n-j-1）…1=n（n-1）…（j＋1）i（i-1）…1 です。

これはnの階乗となる他ありません。
i=jなら自明に成り立ちますが、i≠jならn=i＋jで成り立ち、他の場合はありません。

この回答へのお礼

n!/i!(n-i)!=n(n-1)(n-2)…(n-i+1)/i(i-1)(i-2)…1
n!/j!(n-j)!=n(n-1)(n-2)…(j+1)/(n-j)(n-j-1)(n-j-2)…1

n(n-1)(n-2)…(n-i+1)/i(i-1)(i-2)…1
=n(n-1)(n-2)…(j+1)/(n-j)(n-j-1)(n-j-2)…1

n(n-1)(n-2)…(j+1) i(i-1)(i-2)…1
=n(n-1)(n-2)…(n-i+1) (n-j)(n-j-1)(n-j-2)…1

というわけですね…？
階乗となる他ない、というのはどうしてでしょうか…？

お礼日時：2021/05/25 16:16

No.8 回答者： 大地のしもべ 回答日時： 2021/05/25 15:17

質問者様は（n-k）!を約分した表示を書いてくれましたが、k!を約分した表示もあります。

その二つの表示にiとjを代入して比較すれば、i≠jの条件からi＋j=nと分かると思います。

この回答へのお礼

n(n-1)(n-2)…(i+1)/(n-i)(n-i-1)(n-i-2)…1
=n(n-1)(n-2)…(j+1)/(n-j)(n-j-1)(n-j-2)…1
ということですか？

お礼日時：2021/05/25 15:35