• 検索結果がありません。

組合せの総数nCrが整数であることの証明

N/A
N/A
Protected

Academic year: 2021

シェア "組合せの総数nCrが整数であることの証明"

Copied!
1
0
0

読み込み中.... (全文を見る)

全文

(1)

Math-Aquarium【定理・公式の証明】組合せの総数nCrが整数であることの証明 n 個のものから r 個取った組合せの総数 nCr! ) ( ! ! r n r n - が整数であることを示す。 〈注意〉証明には,数学 B「数列」で学習する数学的帰納法を用います。 〈注意〉「n 個のものから r 個取った組合せの総数」という定義から,nCrが整数(厳密に言えば自然数)で あることは明らか,としてもよいですが,ここでは数学的帰納法を用いた証明を紹介します。

証明

まず,n+1CrnCr-1+nCr (n は自然数,r は 0≦r≦n を満たす整数) が成り立つことを示す。 (右辺)=nCr-1+nCr= ! ) 1 ( ! ) 1 ( ! + - - n r r n + ! ) ( ! ! r n r n - = } ! ) ( ) 1 {( ! ) 1 ( ! r n r n r n - ・ + - - + ( 1)!( )! ! r n r r n - - ・ = ! ) ( ! ) 1 ( ) 1 ( ! ) 1 ( ! r n r r n r n r n n r - - ・ + - ・ + - + ・ = } ! ) ( ) 1 }{( ! ) 1 ( { ! )} 1 ( { r n r n r r n r n r - ・ + - - ・ ・ + - + = ! ) 1 ( ! ! ) 1 ( + - ・ + r n r n n = ! } ) 1 {( ! ! ) 1 ( r n r n - + + =n+1Cr=(左辺) 次に,自然数 n と 0≦r≦n を満たす整数 r に対して,nCrが整数であることを,数学的帰納法を用いて 示す。 (ⅰ) n=1 のとき 0≦r≦1 を満たす整数 r は r=0,1 1C0=1C1=1 より,整数である。 (ⅱ) n=k のとき,0≦r≦k を満たす整数 r に対して,kCrが整数であると仮定する。 このとき,n=k+1 について考える。 k+1Ck+1=k+1C0=1 より,整数である。 ② 1≦r≦k を満たす整数 r に対して, k+1CrkCr-1+kCr であり,仮定よりkCr-1,kCrは整数で あるから,k+1Crは整数である。 ①,②より,n=k+1 のときもnCrは整数である。 (ⅰ),(ⅱ)から,すべての自然数 n と 0≦r≦n を満たす整数 r に対して,nCrは整数である。

ポイント

数学的帰納法を用いるため,n+1CrnCr-1+nCr という式変形を利用する。

コメント

定義式nCr= ! P r r n から,「連続する r 個の整数の積は r ! で割り切れる」ことを示して もよい。 証明その2は,三角形の辺として相似を利用して求める方法です。 このほかにベクトルや,三角関数などを利用した証明があります。 m ! =m・(m-1) ! という 変形を利用する。 1≦r≦k のとき,0≦r-1≦k-1≦k, 0≦1≦r≦k であるから,kCr-1kCrも整数である。

参照

関連したドキュメント

これはつまり十進法ではなく、一進法を用いて自然数を表記するということである。とは いえ数が大きくなると見にくくなるので、.. 0, 1,

解析の教科書にある Lagrange の未定乗数法の証明では,

ここで, C ijkl は弾性定数テンソルと呼ばれるものであり,以下の対称性を持つ.... (20)

、肩 かた 深 ふかさ を掛け合わせて、ある定数で 割り、積石数を算出する近似計算法が 使われるようになりました。この定数は船

しかし , 特性関数 を使った証明には複素解析や Fourier 解析の知識が多少必要となってくるため , ここではより初等的な道 具のみで証明を実行できる Stein の方法

LF/HF の変化である。本研究で はキャンプの日数が経過するほど 快眠度指数が上昇し、1日目と4 日目を比較すると 9.3 点の差があ った。

 同一条件のエコノミークラ ス普通運賃よ り安価である ことを 証明する

としても極少数である︒そしてこのような区分は困難で相対的かつ不明確な区分となりがちである︒したがってその