![見出し画像](https://assets.st-note.com/production/uploads/images/78792159/rectangle_large_type_2_f6a22c440845e23780627e9e23400bd7.png?width=1200)
書記が数学やるだけ#371 完全数列,包除原理
完全数列について性質を確認する。
問題
完全数列は,2022共通テストでも題材にされた。
![スクリーンショット 2022-05-18 11.52.52](https://assets.st-note.com/production/uploads/images/78792154/picture_pc_64fca97238e3765a0653b4eb1c562e98.png?width=1200)
説明
完全順列とは,i 番目が i でない順列である。例えば(1,2,3,4)に対して(2,1,4,3)や(3,1,4,2)などが当てはまる。
![スクリーンショット 2022-05-18 11.48.51](https://assets.st-note.com/production/uploads/images/78791926/picture_pc_c03503af81729d8659e0ebd509352056.png?width=1200)
完全順列の個数をモンモール数ともいい,以下に示す興味深い性質をもつ。
![スクリーンショット 2022-05-18 11.50.25](https://assets.st-note.com/production/uploads/images/78791999/picture_pc_b4898e0e3b7eaa18627b85c686f2d958.png?width=1200)
数え上げの分野において,包除原理は「かつ」「または」をつなぐ。
![スクリーンショット 2022-05-18 11.51.55](https://assets.st-note.com/production/uploads/images/78792092/picture_pc_d1ea0ea603ad102d2c155787c4e4bbb0.png?width=1200)
解答
まずは手計算で数えてみる。
![](https://assets.st-note.com/img/1652855499803-ZNGq2RzVFk.jpg?width=1200)
N5以上は手計算では大変なので,規則性を考えることにする。
まず,a1の決め方は2~5の4通りある。これらを一つ固定して,1をどこに入れるかで2通り考える。最終的に,3項間漸化式として記述できるようになる。
![](https://assets.st-note.com/img/1652855517117-QEAkREbsjR.jpg?width=1200)
![](https://assets.st-note.com/img/1652855629713-n1rcfJJMLk.jpg?width=1200)
あとは一般項を求めるだけ。m!で割るのが重要なヒントとなっている。
![](https://assets.st-note.com/img/1652855624192-NYzUhhN8ed.jpg?width=1200)
包除原理について,n=2,3の場合はお馴染みのベン図でわかる。
![](https://assets.st-note.com/img/1652855674704-kI7alL2VaI.jpg?width=1200)
これを一般化するために共通部分の個数を数え上げる,この過程で二項定理が使える。
![](https://assets.st-note.com/img/1652855736071-WhQb1T0PGK.jpg?width=1200)
包除原理を利用したモンモール数の導出について。
![](https://assets.st-note.com/img/1652855784944-LKEs0Xd4xk.jpg?width=1200)
本記事のもくじはこちら:
学習に必要な本を買います。一覧→ https://www.amazon.co.jp/hz/wishlist/ls/1XI8RCAQIKR94?ref_=wl_share