2003　京都大学　後期情報論述問題MathJax

【１】　$n$を正の整数とするとき，$1$から$n$までの$n$個の整数が任意の順序で並んだ列を，整数列と呼ぶことにし，$n$を整数列の長さと呼ぶ．整数$a_1\text{，}{a}_2\text{，}\cdots \text{，}{a}_n$がこの順に並んだ整数列を，$[a_1,a_2,\cdots ,a_n]$と表記する．たとえば，長さ$3$の整数列には，次の$6$つがある．

$[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]$

長さ$n$の整数列が$1$つ与えられたときに，隣接する$2$つの整数の順序を入れ換えることを繰り返して，昇順列，つまり整数が小さいものから順に並んだ整数列$[1,2,\cdots ,n]$に変換したい．隣接する$2$つの整数の順序を入れ換えるのは，整数$l$と，その直後の整数$m$が，$l>m$を満たす場合だけである．この操作を，スワップと呼ぶことにする．たとえば，整数列$[3,2,1]$に対しては，スワップを$3$回行う次の手順で，昇順列に変換できる．ここで，矢印「$\to$」は，$1$回のスワップを表す．また，それぞれのスワップによって入れ換えられる整数を，下線で示す．

$[\underline{3},\underline{2},1]\to [2,\underline{3},\underline{1}]\to [\underline{2},\underline{1},3]\to [1,2,3]$(1)

この変換に関して，以下の問題に答えよ．

[問題１]　$1$つの整数列に対して，スワップできる整数の組が，$2$つ以上存在することがある．たとえば，$[3,2,1]$に対しては，$3$と$2$をスワップしてもよいし，$2$と$1$をスワップしてもよい．したがって，与えられた整数列を昇順列に変換する手順は，$1$通りとは限らない．たとえば，$[3,2,1]$に対しては，上の(1)の手順以外に，次の手順がある．

$[3,\underline{2},\underline{1}]\to [\underline{3},\underline{1},2]\to [1,\underline{3},\underline{2}]\to [1,2,3]$

しかし，与えられた整数列を昇順列に変換するために必要なスワップの回数は，手順とは関係なく一定である．このことを証明せよ．

[問題２]　与えられた整数列を昇順列に変換するために必要なスワップの回数を，以下では単にスワップ数と呼ぶことにする．長さ$n$のすべての整数列のうちで，スワップ数が最大になるのは，降順列，つまり整数が大きいものから順に並んだ整数列$[n,\cdots ,2,1]$だけである．このことを証明せよ．

[問題３]　長さ$n$のすべての整数列のスワップ数の総和を，$T(n)$と表す．$n=1$のとき，長さ$1$の唯一の整数列$[1]$は昇順列なので，スワップ数は$0$である．したがって，$T(1)=0$である．また，長さ$2$の整数列$[1,2]$と$[2,1]$のスワップ数は，それぞれ$0$と$1$なので，$T(2)=1$である．$2$以上の整数$n$に対して，$T(n)$を，$T(n-1)$を使って表す漸化式を導け．

[問題４]　長さ$n$の整数列は，全部で$n!$個ある．これらのスワップ数の平均値

$A(n)={\displaystyle \frac{T(n)}{n!}}$

を表す$n$の多項式を導け．

[問題５]　整数列の先頭から順に整数を調べていって，スワップ可能な組があればスワップする，という一連の処理を，スキャンと呼ぶことにする．つまり，$1$回のスキャンでは，$i$番目（$1\leqq i<n$）の整数と，その直後の$i+1$番目の整数がスワップ可能であればスワップする，ということを，$i$を$1$から順に$n-1$まで繰り返すのである．たとえば，$[3,2,1]$をスキャンすると，まず先頭の$3$が$2$とスワップされて$[2,3,1]$となり，次に$[2,3,1]$の$2$番目の整数$3$が$1$とスワップされて$[2,1,3]$が得られる．したがって，$1$回のスキャンによって，$[3,2,1]$は，$[2,1,3]$に変換される．このことを次のように表記する．

$[3,2,1]⟹[2,1,3]$

スキャンを何回か繰り返すことによって，与えられた整数列を昇順列に変換することを考える．整数列を$1$回スキャンして，もしスワップが一度も行われなければ，その整数列はすでに昇順列なので，変換は終了する．スキャンを$1$回行って，もしスワップが一度でも行われれば，もう一度スキャンする．これを，スキャン中にスワップが一度も行われなくなるまで繰り返す．たとえば，$[3,2,1]$に対しては，次のように$2$回のスキャンで昇順列に変換でき，さらに$3$回目のスキャンで，昇順列になっていることを確認できる．

$[3,2,1]⟹[2,1,3]⟹[1,2,3]⟹[1,2,3]$

したがって，$[3,2,1]$を昇順列に変換するためには，$3$回のスキャンを必要とする．

　長さ$n$の任意の整数列を昇順列に変換するために必要なスキャンの回数は，$n$以下であることを証明せよ．

[問題６]　長さ$n$の整数列で，昇順列に変換するために$n$回のスワップを必要とする整数列全体を考える．そのような整数列のうちで，スワップ数が最大のものは，それぞれの$n$について$1$つずつ存在する．その整数列を求め，それが長さ$n$の整数列のなかで唯一のものであることを示せ．

[問題７]　長さ$n$の整数列で，昇順列に変換するために$n$回のスキャンを必要とする整数列全体を考える．そのような整数列のうちで，スワップ数が最小のものは，それぞれの$n$について$1$つずつ存在する．その整数列を求め，それが長さ$n$の整数列のなかで唯一のものであることを示せ．