スタッフBLOG

解答を書きます!!!(やっと書ける…)2016年02月20日

先日出した問題の解答を書こうと思います。

問題文は下のリンクからもう一度眺め直してください。

http://www.shingaku-jyuku.com/blog/%E9%9B%A3%E5%95%8F.html

 

1-nまでのn個の自然数を1列に並べる。

その配列のうち2つの数を選んだ時

左側の数>右側の数

となるような個数を数えることにする。

さて、いま全ての並べ方についてこの個数を数えたとき

その合計はいくつになるか。

 

さて、この問題の解き方なのですが、

(i)

n個の数字を並べる並べ方ははn!通りあります。(=n×(n-1)×(n-2)×…×2×1)

そのうちの1つの並べ方を考えたとき

n個の列から2つの数字を取ってくる方法はnC2=n×(n-1)/2通りありますね。

 

(ii)

今回n個の数字は全部バラバラなので

n個の列から2つの数字を取って来た時、その2つの数の大小は

左側の数>右側の数

または

左側の数<右側の数

になるはずです。(イコールがない、というところがポイントです。)

 

(iii)

実は今回の問題

条件を

左側の数<右側の数

としても求める場合の数は変わりませんね。

(数字を全部右左逆転させて並べたものを考えれば明らかですね)

 

以上(i),(ii),(iii)を合わせて考えると

 

(i)で求めたn!×nC2というすべての比較対象に関して

(ii)で考えたように必ず左右どちらかの値が大きくなるようになっていて

(iii)で考えたようにその総数は左が大きい場合、右が大きい場合それぞれで同じです。

 

つまり

(n!×nC2)/2が求める答えですね。

 

本当は場合の数の漸化式とか立てれば解けるとか思っていたんですが

もう少し簡単な問題でしたね。

 

問題文が難しいだけの問題でした…。

 

河合