問題
場所1から場所 に異なる 個のものが並んでいる。これらを並べ替えてどれもが元の位置にならないようにする方法の総数を とする。ただし とする。
(1) の場合の並べ替え方をすべて書き出して， を求めよ。
(2) に対して を証明せよ。
出典：東京工業大学 2004年度 後期 後期・理系 第1問
方針
(1)は元の場所の番号をものの番号として，場所1から4に入るものの番号列を書き出す。(2)は最後の場所に入るものを1つ決め，そのものの元の場所にもの が入る場合と入らない場合に分ける。前者は残り 個の完全な並べ替え，後者は標準的な置き換えで 個の完全な並べ替えと一対一に対応する。
解答
(1)
並べ替えを，場所1から場所4にあるものの番号の列で表す。どの場所にも元の番号が入らないものはの9通りである。したがって である。
(2)
場所 に入るものを考える。これはもの ではないから， 通りある。そのものを とする。
まず，場所 にもの が入る場合を考える。このとき場所 と場所 では互いに入れ替わっているので，残りの 個について，どれも元の位置にない並べ替えをすればよい。したがってこの場合は 通りである。
次に，場所 にもの が入らない場合を考える。この並べ替えから，場所 にあるもの を取り除く。さらに，もの が入っている場所にもの を入れ直すと，場所1から場所 までにもの1からもの が並び，どれも元の位置にない並べ替えになる。逆に， 個のそのような並べ替えで，もの が入っている場所のものを に替え，場所 にもの を入れれば，今考えている場合の並べ替えがただ1つ得られる。よってこの場合は 通りである。
以上より，場所 に入るもの の選び方が 通りあり，それぞれについて 通りあるから である。