京都大学 1993年度後期・理系数学後期第5問解答・解説

問題

$n ≧ 3$ とする． $1, 2, \dots, n$ のうちから重複を許して6個の数字をえらびそれを並べた順列を考える．このような順列のうちで，どの数字もそれ以外の5つの数字のどれかに等しくなっているようなものの個数を求めよ．

出典：京都大学 1993年度後期日程第2次学力試験後期・理系後期第5問

各数字の出現回数に1がないことが条件である。6の分割のうち各部分が2以上となる $6, 4 + 2, 3 + 3, 2 + 2 + 2$ に分け、数字の選択と並べ方を掛ける。

使われる数字の出現回数はすべて2以上で、合計が6である。可能な型は

6, 4 + 2, 3 + 3, 2 + 2 + 2

だけである。

それぞれの個数は

n,

n (n - 1) \frac{6 !}{4 ! 2 !} = 15 n (n - 1),

_{n} C_{2} \frac{6 !}{3 ! 3 !} = 10 n (n - 1),

_{n} C_{3} \frac{6 !}{2 ! 2 ! 2 !} = 15 n (n - 1) (n - 2)

である。従って総数は

n + 25 n (n - 1) + 15 n (n - 1) (n - 2) = 15 n^{3} - 20 n^{2} + 6 n .