高知大学理学部・医学部 2017年問題3

画像
HTML版

$nは正の整数とする．1からnまでの異なるn個の整数の順列を考える．以下そのような順列に対して，直前の数よりも小さい数が並ぶ回数を「下降回数」と呼ぶ．例えば，n=4のとき，1432では4の次に3，3の次に2が並んでいるので下降回数は2である．同様にして1234，1324，4321の下降回数はそれぞれ0，1，3である．下降回数が1である順列の総数をa_n，下降回数が2である順列の総数をb_nとおく．このとき，次の問いに答えよ．(1)a_4を求めよ．(2)a_n=Σ_{k=0}^n(\comb{n}{k}-1)であることを示せ．(3)a_nを求めよ．(4)n≧2のとき，b_n=Σ_{k=1}^{n-1}\comb{n}{k}a_{n-k}-Σ_{m=1}^{n-1}(m-1)(\comb{n}{m}-1)であることを示せ．$