反転数の和

  • 公開日時: 2020/04/18 20:47
  • 閲覧数: 577
  • コメント数: 5
  • カテゴリ: 入試・教育

[式:…]の順列をひとつ考えてそれを[式:…]とします。

このとき順列[式:…]の反転数とは、[式:…]となる組[式:…]の個数とします。

 

[式:…]で順列[式:…]を考えると([式:…])、

[式:…]より右に[式:…]があり、[式:…]より右に[式:…]があり、[式:…]より右に[式:…]があるので、

順列[式:…]の反転数は[式:…]となります。

 

 

問題

[式:…]の順列[式:…] 個全ての反転数を足し合わせた値を[式:…]で表してください。

公序良俗に反する不適切な投稿を発見された方はこちらよりご報告ください

この投稿にフォローする

コメントをつけるにはログインが必要です。

全件表示

No メッセージ 投稿者 日時    
1
1,2,3,・・・,nの順列n!個全ての反転数を足し合わせた値を[式:…]
とする。
[式:…]
これより,[式:…]
クロニャンコ さん 2020/04/19 11:15:01 報告
2
ありがとうございます。
漸化式で考えると、順列の反転数の期待値もすぐに分かってしまうのですね。

横浜市立大学の問題 https://suugaku.jp/kako/yokohamashiritsu/19183.html でした。
アンドロメダ さん 2020/04/19 16:52:22 報告
3
おじゃま虫です。

或る i<j の組に注目します。
1つの順列 a1,a2, ai,・・・,aj,・・・・,an と
その(ai,aj)だけ入れ替えた順列と
は1:1で対応しています。
その一方は ai < aj (反転数0) で、もう一方は ai > aj (反転数1) です。

∴ n!個の順列のうち
 ai < aj となる順列  (反転数 0) と
 ai > aj となる順列  (反転数 1)
は同数あり、したがって n!/2 個ずつです。

また i<j となる組は全部で C(n,2)= n(n-1)/2 組あります。

それを掛けたものが答え(総数)です。
prime_132 さん 2020/04/20 10:53:30 報告
4
prime132さん
スマートな解答ですね。
クロニャンコ さん 2020/04/20 21:08:48 報告
5
本当にスマートですね。
横浜市立大学の[式:…]をまともに計算した私の立場は…。

[式:…]の順列[式:…]個のうち反転数が[式:…]のものがいくつあるか?
というのはなかなか考えがいのある問題のようで、
[式:…]
という多項式を展開したときの [式:…] の係数になるそうです。
アンドロメダ さん 2020/04/24 16:37:46 報告