この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

離散数学・組合せ論の問題

難易度 2教科書の演習問題レベル証明問題大学数学離散数学・組合せ論

正の整数 $n$ に対し、集合 ${1, 2, \dots, n}$ 上の置換（ ${1, 2, \dots, n}$ からそれ自身への全単射） $σ$ で、すべての $i (1 \leq i \leq n)$ について $σ (i) \neq = i$ を満たすもの（攪乱順列）の個数を $D_{n}$ とする。

包除原理を用いて、正の整数 $n$ について「 $D_{n}$ が偶数であることと、 $n$ が奇数であることは同値である」ことを証明せよ。

この問題で使うもの

攪乱順列（説明と入口の問題）
一般の包除原理（説明と入口の問題）
組合せ（説明と入口の問題）

この問題を解けるようになるまで（10 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

まず包除原理で $D_{n}$ を表す公式を作り、その公式から $D_{n}$ と $D_{n - 1}$ の関係式を導きます。偶奇は帰納法で決めます。

ヒント 2

$A_{i} = {σ : σ (i) = i}$ とおくと、 $j$ 個の $A_{i}$ の共通部分の大きさは $(n - j)!$ です。これから $D_{n} = \sum_{j = 0}^{n} (- 1)^{j} \frac{n !}{j !}$ が得られます。

ヒント 3

この公式から $n D_{n - 1}$ を引くと、最後の項だけが残って $D_{n} - n D_{n - 1} = (- 1)^{n}$ になります。あとは $D_{1} = 0$ から始めて、 $n$ の偶奇で場合分けします。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$A_{i} = {σ : σ (i) = i}$ のように「 $i$ を固定する置換の集合」を定め、攪乱順列がどの $A_{i}$ にも属さない置換であるとして包除原理を適用している（2 点）
$j$ 個の $A_{i}$ の共通部分の個数が $(n - j)!$ であることを理由付きで述べ、 $D_{n} = \sum_{j = 0}^{n} (- 1)^{j} \frac{n !}{j !}$ を導いている（3 点）
公式から $D_{n} - n D_{n - 1} = (- 1)^{n} (n \geq 2)$ を計算で導いている（2 点）
$D_{1} = 0$ を基点に、 $n$ の偶奇で場合分けした帰納法で偶奇を決定し、同値性を結論している（3 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

方針: 包除原理で $D_{n}$ の公式を求め、そこから漸化式 $D_{n} = n D_{n - 1} + (- 1)^{n} (n \geq 2)$ を導く。最後に $n$ についての帰納法で偶奇を決める。

ステップ 1: 包除原理による公式。 $S_{n}$ を ${1, \dots, n}$ 上の置換全体（ $∣ S_{n} ∣ = n!$ ）とし、 $i = 1, \dots, n$ に対して $A_{i} = {σ \in S_{n} : σ (i) = i}$ とおく。攪乱順列はどの $A_{i}$ にも属さない置換なので、包除原理より
$D_{n} = j = 0 \sum n (- 1)^{j} 1 \leq i_{1} < \dots < i_{j} \leq n \sum ∣ A_{i_{1}} \cap \dots \cap A_{i_{j}} ∣$
（ $j = 0$ の項は $∣ S_{n} ∣ = n!$ ）。 $A_{i_{1}} \cap \dots \cap A_{i_{j}}$ は $i_{1}, \dots, i_{j}$ を固定する置換全体であり、そのような置換は残りの $n - j$ 個の元の上の置換と 1 対 1 に対応するので、その個数は $(n - j)!$ である。 $j$ 個の添字の選び方は $(j n)$ 通りなので
$D_{n} = j = 0 \sum n (- 1)^{j} (j n) (n - j)! = j = 0 \sum n (- 1)^{j} \frac{n !}{j !} . (1)$

ステップ 2: 漸化式。 $n \geq 2$ とする。 $(1)$ を $n - 1$ （正の整数）に用いて $n$ 倍すると
$n D_{n - 1} = n \cdot (n - 1)! j = 0 \sum n - 1 \frac{( - 1 ) ^{j}}{j !} = j = 0 \sum n - 1 (- 1)^{j} \frac{n !}{j !} .$
これを $(1)$ から引くと、 $j = n$ の項だけが残り
$D_{n} - n D_{n - 1} = (- 1)^{n} \frac{n !}{n !} = (- 1)^{n}, すなわち D_{n} = n D_{n - 1} + (- 1)^{n} (n \geq 2) . (2)$

ステップ 3: 帰納法。 正の整数 $n$ についての命題 $P (n)$ :「 $n$ が奇数なら $D_{n}$ は偶数、 $n$ が偶数なら $D_{n}$ は奇数」を数学的帰納法で示す。これは「 $D_{n}$ が偶数 $⟺$ $n$ が奇数」と同値である（ $n$ も $D_{n}$ も整数で、偶数か奇数のどちらか一方なので）。

$n = 1$ のとき: ${1}$ 上の置換は恒等置換だけで、 $σ (1) = 1$ なので $D_{1} = 0$ 。 $n = 1$ は奇数で $D_{1}$ は偶数なので $P (1)$ は成り立つ（ $(1)$ でも $D_{1} = 1 - 1 = 0$ ）。
$n \geq 2$ で $P (n - 1)$ を仮定して $P (n)$ を示す。 $(2)$ を使う。
$n$ が奇数のとき: $n - 1$ は偶数なので仮定より $D_{n - 1}$ は奇数。 $n$ も奇数なので $n D_{n - 1}$ は奇数で、 $(- 1)^{n} = - 1$ を加えた $D_{n} = n D_{n - 1} - 1$ は偶数。
$n$ が偶数のとき: $n D_{n - 1}$ は偶数 $n$ の倍数なので偶数で、 $(- 1)^{n} = 1$ を加えた $D_{n} = n D_{n - 1} + 1$ は奇数。

どちらの場合も $P (n)$ が成り立つ。

帰納法により、すべての正の整数 $n$ で $P (n)$ が成り立つ。

（確認: $D_{1}, D_{2}, D_{3}, D_{4}, D_{5} = 0, 1, 2, 9, 44$ 。）

以上より、正の整数 $n$ について、 $D_{n}$ が偶数であることと $n$ が奇数であることは同値である。 $■$

離散数学・組合せ論の問題

この問題で使うもの

ヒント

採点の観点と模範解答

次のおすすめ

この問題の確認

間違いを報告する

関連する問題