つまり、組合せを計算する際の分子は必ず分母で割りきれるわけ。
これって、誰も言わないけど、かなり驚きのことだと思う。
例えば、10×9×8×7×6が5×4×3×2×1で割りきれるかって考えてみてほしいんだけど、計算しないですぐわかる?
直感的にはわからないじゃん。でもこれって、10C5の分子と分母だから、割りきれるわけですよ。
他にも、111×110×99×98×97×96×95が7×6×5×4×3×2×1で割れるとか、わからないでしょ。
すごさがわかったよね?
すなわち、組合せnCrって、任意の整数nから下に連続するr個の整数を、r×r-1×…×2×1で割った値だけど、
こんな変な割り算が、自然数nとrがどんな値でも常に整数になるなんて驚き!!
マジすごくない?
マジですごいと思うのに、誰も感動してないから、教養の殿堂たる増田に書き込んでみたよ!
(追記)
ちょっと証明してみるかーと思ったら思いの外手こずった。ググったらパスカルの等式っていうのが出てきてこれがわかれば帰納法でいけるのか。この等式自体もなかなか面白い
なるほど。
パスカルの三角形ってやつで、一番上が整数だから下側は全部整数になるってわけか。
厳密な証明をするまでもないよ。
7個の数字が並んでいたらどこかに7で割れる数字が混じっている。n個の数字が並んでいたらどこかにnで割れる数字が混じっている。
いやいや、重複があるかもしれないじゃん。
この説明もわかりやすいとは思ったんだけど、証明としてはダメなのかな?
ほんとそれ。整数論的にちゃんと証明するにはルジャンドルの定理的な考察が必要。
分からない人は高校数学の美しい物語の記事: https://manabitimes.jp/math/589 を見て、どうぞ。
https://anond.hatelabo.jp/20220305162311 2nCn はさらに n+1 で割れる!(つまり 2n×(2n-1)×...×(n+1) は (n+1)! = (n+1)×n×...×1 で割れる。) これがいわゆるカタラン数。
そんなこと言われてもワカラン数
カタラン数について語らんか?
すごいと思ってたけど、n進数を学ぶとn個に1個割れるの出てくるの当然かと納得した。
分母=r個の連続した整数の積 分子=r個の連続した整数の積 分子の各々の整数の倍数は分母に当然現れる。 はい、論破。
nCrで、r=n-1かr=1の時・・・分母が1なので自然数。 r=それ以外のとき、「n 個の連続する自然数には、必ず n の倍数が含まれる」ので必ず自然数。 例(14C3=14*13*12÷3*2*1だと、部分的に14÷2が...
これが試験の答案だったら部分点1/3ってとこだな。
クロムなんとか化物の話だと思うんだけど、違う?