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

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

$$\sigma (1)\ne 1,\sigma (1)\ne 2,\sigma (2)\ne 1,\sigma (3)\ne 3,\sigma (4)\ne 4$$

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

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

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

集合 $\{1,2,3,4,5\}$ の置換（$\{1,2,3,4,5\}$ から自分自身への全単射）$\sigma$ を、互いに素な巡回置換の積に分解する。ただし、不動点も長さ $1$ の巡回として数える。巡回の個数がちょうど $2$ 個であるような置換 $\sigma$ の個数を求めよ。

集合 $\{1,2,3,4,5,6,7\}$ からそれ自身への全単射（置換）$\sigma$ のうち、次の 2 つの条件をともに満たすものの個数を求めよ。

• すべての $i$ $(1\le i\le 7)$ について $\sigma (i)\ne i$
• すべての $i$ $(1\le i\le 6)$ について $\sigma (i)\ne i+1$

（たとえば $7$ 人の生徒 $1,\dots ,7$ が席替えをするとき、生徒 $i$ が元の席 $i$ にも右隣の席 $i+1$ にも座らないような座り方の数に当たる。席 $7$ の右隣は考えない。）

0 以上の整数 $a,b,c$ の組 $(a,b,c)$ で、
$$a+b+c=10,a\text{ は偶数},b\le 3$$
を満たすものの個数を求めよ。