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

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

難易度 1教科書の例題レベル大学数学離散数学・組合せ論

集合 ${1, 2, 3, 4}$ からそれ自身への全単射（置換） $σ$ のうち、次の条件をすべて満たすものの個数を求めよ。

$σ (1) \neq = 1, σ (1) \neq = 2, σ (2) \neq = 1, σ (3) \neq = 3, σ (4) \neq = 4$

ただし、 $4 \times 4$ のマス目の第 $i$ 行第 $j$ 列のマスを $(i, j)$ で表し、 $σ (i) = j$ を「マス $(i, j)$ を使う」と考えるものとする。禁止されるマスは $(1, 1), (1, 2), (2, 1), (3, 3), (4, 4)$ の $5$ 個である。

この問題で使うもの

禁止位置のある順列とルーク多項式（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

禁止されるマスを盤とみなし、ルーク多項式の係数 $r_{k}$ を求めて $\sum_{k} (- 1)^{k} r_{k} (4 - k)!$ を計算する技能を使う。

ヒント 2

盤は ${(1, 1), (1, 2), (2, 1)}$ と ${(3, 3)}$ と ${(4, 4)}$ に分かれ、互いに行も列も共有しない。それぞれのルーク多項式 $1 + 3 x + x^{2}$ , $1 + x$ , $1 + x$ の積を考えるとよい。

ヒント 3

$r_{0} = 1, r_{1} = 5, r_{2} = 8, r_{3} = 5, r_{4} = 1$ となる。これを $r_{0} \cdot 4! - r_{1} \cdot 3! + r_{2} \cdot 2! - r_{3} \cdot 1! + r_{4} \cdot 0!$ に代入する。

答えと解説

答えを見る

6

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

解説を読む

方針　禁止マスの集まり（盤） $B = {(1, 1), (1, 2), (2, 1), (3, 3), (4, 4)}$ に、どの 2 個も同じ行・同じ列にないように $k$ 個のルークを置く方法の数を $r_{k}$ とする。禁止位置をすべて避ける置換の個数は
$N = k = 0 \sum 4 (- 1)^{k} r_{k} (4 - k)!$
で求められる（ $r_{k}$ 個の配置それぞれについて、残りの $4 - k$ 行を残りの列に自由に対応させる $(4 - k)!$ 通りを包除原理で足し引きする）。

$r_{k}$ を求める

- $r_{0} = 1$ （何も置かない）。
- $r_{1} = 5$ （禁止マスは $5$ 個）。
- $r_{2}$ ： $5$ 個から $2$ 個を選ぶ方法は $_{5} C_{2} = 10$ 通り。このうち同じ行または列にあるのは $(1, 1)$ と $(1, 2)$ （第 1 行）、 $(1, 1)$ と $(2, 1)$ （第 1 列）の $2$ 組だけなので、 $r_{2} = 10 - 2 = 8$ 。
- $r_{3}$ ：盤は「 $(1, 1), (1, 2), (2, 1)$ の部分」と「 $(3, 3)$ 」「 $(4, 4)$ 」に分かれ、これらは互いに行も列も共有しない。前者の部分に置けるのは、 $1$ 個なら $3$ 通り、 $2$ 個なら ${(1, 2), (2, 1)}$ の $1$ 通りだけ。
- 前者に $2$ 個、 $(3, 3), (4, 4)$ から $1$ 個： $1 \times 2 = 2$ 通り
- 前者に $1$ 個、 $(3, 3), (4, 4)$ の両方： $3 \times 1 = 3$ 通り
よって $r_{3} = 2 + 3 = 5$ 。
- $r_{4}$ ：前者に $2$ 個 ${(1, 2), (2, 1)}$ と $(3, 3), (4, 4)$ を置く $1$ 通りだけなので $r_{4} = 1$ 。

（ルーク多項式は $R (x) = (1 + 3 x + x^{2}) (1 + x)^{2} = 1 + 5 x + 8 x^{2} + 5 x^{3} + x^{4}$ となり、上の値と一致する。）

公式に代入する
$N = 1 \cdot 4! - 5 \cdot 3! + 8 \cdot 2! - 5 \cdot 1! + 1 \cdot 0! = 24 - 30 + 16 - 5 + 1 = 6$

確認　 $σ (1) \in {3, 4}$ である。 $σ (1) = 3$ のとき $(σ (2), σ (3), σ (4))$ は $(2, 4, 1), (4, 1, 2), (4, 2, 1)$ の $3$ 通り、 $σ (1) = 4$ のとき $(2, 1, 3), (3, 1, 2), (3, 2, 1)$ の $3$ 通りで、合計 $6$ 通りとなり一致する。

よって求める個数は $6$ である。

別解

禁止マスは $(1, 1), (1, 2), (2, 1)$ のかたまりと、孤立した $(3, 3)$ 、 $(4, 4)$ からなる。

ルーク多項式を求める。
- $(1, 1), (1, 2), (2, 1)$ の部分では、1 個の置き方は 3 通りである。2 個の置き方は $(1, 2)$ と $(2, 1)$ の組だけなので 1 通りである。よって $1 + 3 x + x^{2}$ 。
- 孤立したマス 1 個につき $1 + x$ 。

全体は $(1 + 3 x + x^{2}) (1 + x)^{2} = 1 + 5 x + 8 x^{2} + 5 x^{3} + x^{4}$ となる。

包除原理より、求める個数は
$4! - 5 \cdot 3! + 8 \cdot 2! - 5 \cdot 1! + 1 \cdot 0! = 24 - 30 + 16 - 5 + 1 = 6$ 。

検算として直接数える。 $σ (1) \in {3, 4}$ である。
- $σ (1) = 3$ のとき、残りの行 2,3,4 は列 1,2,4 に対応する。条件を満たすのは 3 通りである。
- $σ (1) = 4$ のとき、残りの行 2,3,4 は列 1,2,3 に対応する。条件を満たすのは 3 通りである。

合計 6 通りとなり、包除原理の結果と一致する。

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題