次のような場合分けの数を場合の数として求めてみたいのだが,どうしたらよいだろうか。
実数全体を3つの区間に分け,二つの実数 x と y がそれぞれの区間に入っている場合を虱潰しに調べたい。
ただし場合分けの数を減らすため,x<y であると仮定する。
実数全体を3つに分ける区切りとなる数を a,b とおく。ただし a<b とし,これらの数を , であらわすことにする。
数直線においては実数は左から右へと小さいものから大きいものを並べて行くので,それに従って図示すると次のようになる。
(1) 右右
[ , ,xy]
(2) 中右
[ ,x,y]
(3) 左右
[x, ,y]
(4) 中中
[ ,xy, ]
(5) 左中
[x,y, ]
(6) 左左
[xy, , ]
この数え方から示唆されることは,もし実数全体が n 個の区間に分割された場合,検討すべき場合の総数は,y が右から数えて何番目の区間にいるかを表す数 k と,x の位置を表す数 m を用いて
Σ[k=1~n](Σ[m=1~k]1))=Σ[k=1~n] k =n(n+1)/2
と計算することができる。これは高校の数列の単元で教わる基本的な数列の和の公式そのものである。
あるいは,次のように考えても同じ結果を導ける。
まず,x と y の大小関係を気にせずに,x と y をそれぞれ n 個の区間のどこかに入れる方法は n2 通りある。
それらの場合は,
(イ)x が y よりも左側の区間にあるもの。
(ロ)x と y が同じ区間にあるもの。
(ハ)x が y よりも右側の区間にあるもの。
の3つに大別される。これらは互いに排反である(2つ以上の場合が同時に起こることはない)。
さて,必要なのは(イ)と(ロ)の場合の合計のみである。
対称性を考慮すると,(イ)の場合の数と(ハ)の場合の数は同じはずである。
また,(ロ)は n 通りである。
よって,
(イ)+(ロ)+(ハ)=n2,
(イ)=(ハ),
(ロ)=n
であるから,まず
2×(イ)+(ロ)=n2
であり,両辺に(ロ)を加えると
2×((イ)+(ロ))=n(n+1)
なので,両辺を 2 で割れば所望の答えを得る。
実数全体を3つの区間に分け,二つの実数 x と y がそれぞれの区間に入っている場合を虱潰しに調べたい。
ただし場合分けの数を減らすため,x<y であると仮定する。
実数全体を3つに分ける区切りとなる数を a,b とおく。ただし a<b とし,これらの数を , であらわすことにする。
数直線においては実数は左から右へと小さいものから大きいものを並べて行くので,それに従って図示すると次のようになる。
(1) 右右
[ , ,xy]
(2) 中右
[ ,x,y]
(3) 左右
[x, ,y]
(4) 中中
[ ,xy, ]
(5) 左中
[x,y, ]
(6) 左左
[xy, , ]
この数え方から示唆されることは,もし実数全体が n 個の区間に分割された場合,検討すべき場合の総数は,y が右から数えて何番目の区間にいるかを表す数 k と,x の位置を表す数 m を用いて
Σ[k=1~n](Σ[m=1~k]1))=Σ[k=1~n] k =n(n+1)/2
と計算することができる。これは高校の数列の単元で教わる基本的な数列の和の公式そのものである。
あるいは,次のように考えても同じ結果を導ける。
まず,x と y の大小関係を気にせずに,x と y をそれぞれ n 個の区間のどこかに入れる方法は n2 通りある。
それらの場合は,
(イ)x が y よりも左側の区間にあるもの。
(ロ)x と y が同じ区間にあるもの。
(ハ)x が y よりも右側の区間にあるもの。
の3つに大別される。これらは互いに排反である(2つ以上の場合が同時に起こることはない)。
さて,必要なのは(イ)と(ロ)の場合の合計のみである。
対称性を考慮すると,(イ)の場合の数と(ハ)の場合の数は同じはずである。
また,(ロ)は n 通りである。
よって,
(イ)+(ロ)+(ハ)=n2,
(イ)=(ハ),
(ロ)=n
であるから,まず
2×(イ)+(ロ)=n2
であり,両辺に(ロ)を加えると
2×((イ)+(ロ))=n(n+1)
なので,両辺を 2 で割れば所望の答えを得る。
※コメント投稿者のブログIDはブログ作成者のみに通知されます