山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

行と列の入れ替えに関する問題

数学

行と列の入れ替え

アルゴリズムパズル プログラマのための数学パズル入門を読んでいて気になったことを書きます。

アルゴリズムパズル ―プログラマのための数学パズル入門

アルゴリズムパズル ―プログラマのための数学パズル入門

次の n行 n 列の行列の要素が 1～n^2の自然数で埋められているとします。

　 　　 　　 　
1 2 \cdots n
n+1 n+2 \cdots 2n
\vdots \vdots \ddots \vdots
n(n-1) + 1 n(n-1) +2 \cdots n^2

上記の行列を Aとして、行の入れ替えと列の入れ替えによる問題を考えます。また、行の入れ替えと列の入れ替えを操作と呼ぶことにします。列の入れ替えとは、第 i列を a_iとしたとき、行列を A = [ a_1, a_2, \cdots , a_n]と表し、 1列目と 2列目を入れ替えてできる行列は [ a_2 , a_1, \cdots , a_n ] のようになります。

任意の回数操作を行って得られる行列のパターン

行列のパターンとは、操作によって得られた行列が A_i \neq A_jとなるものです。

行列ではなく、一次元で数字の並びを考えると、数字が n 種類あるので、これらの並び方なので、 n! 通りあることが分かります。

これを行列に拡張して考えると、操作によって得られる行列のパターンは (n!)^2 通りあります。たぶん合ってる？

また、 n^2 種類の数字を行列に配置するパターンは (n^2)! 通りあります。操作によって得られるパターンと比較すると、

(n!)^2 \lt (n^2)!

となることが分かります。

この行列の操作によって変わらないものは何かといいますと、行または列の要素は変わらないということです。つまり、同じ行にある要素は操作によって変化、順序だけが変わるということです。考えてみれば当たり前のことですが、言われるまで気が付きませんでした。

操作によって得られる行列の要素が元の位置にある個数の期待値

操作によって得られる行列のパターンは (n!)^2 通りあるとして、その各行列にたいして元の位置にある要素の期待値を考えます。

例えば、 1は最初元の行列の (1, 1)成分にあります。操作によって得られた行列に対して 1 が存在する成分が (1, 1) であれば元の位置にあるとして、個数を1数えます。このことを全ての行列のパターンにたいして、元の位置にある要素がいくつあるのかという期待値を考えます。

これも期待値の線形性から導けると思います。

うーん。どうやって解くんだろ。

感想

いつもは問題を受動的に考えるだけでしたが、今回は自発的に問題を考えてみました。答えがないので、合っているかはわかりません。