書記が数学やるだけ#371 完全数列，包除原理

完全数列について性質を確認する。

問題

完全数列は，2022共通テストでも題材にされた。

説明

完全順列とは，i 番目が i でない順列である。例えば(1,2,3,4)に対して(2,1,4,3)や(3,1,4,2)などが当てはまる。

完全順列の個数をモンモール数ともいい，以下に示す興味深い性質をもつ。

数え上げの分野において，包除原理は「かつ」「または」をつなぐ。

解答

まずは手計算で数えてみる。

N5以上は手計算では大変なので，規則性を考えることにする。

まず，a1の決め方は2~5の4通りある。これらを一つ固定して，1をどこに入れるかで2通り考える。最終的に，3項間漸化式として記述できるようになる。

あとは一般項を求めるだけ。m!で割るのが重要なヒントとなっている。

包除原理について，n=2,3の場合はお馴染みのベン図でわかる。

これを一般化するために共通部分の個数を数え上げる，この過程で二項定理が使える。

包除原理を利用したモンモール数の導出について。

本記事のもくじはこちら：