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

$1$ から $7$ の順列全体（$7!=5040$ 個）を全体集合とし、$i=1,2,\dots ,6$ に対して
$$A_i=\{\text{順列の中で }i\text{ のすぐ右隣に }i+1\text{ があるもの}\}$$
とおく。求めるのは $A_1,\dots ,A_6$ のどれにも属さない順列の個数である。

共通部分の大きさ. 添字の集合 $T\subset \{1,\dots ,6\}$, $|T|=t$ を選ぶ。${\bigcap }_{i\in T}{A}_i$ に属する順列では、各 $i\in T$ について「$i,i+1$」が隣り合って並ぶ。たとえば $T=\{2,3\}$ なら $2,3,4$ がこの順に連続して並ぶ。このように $T$ の各要素ごとに $i$ と $i+1$ を貼り合わせると、7 個の数は $7-t$ 個のかたまり（連続して並ぶ数の列）にまとまり、各かたまりの中の並び順は決まっている。逆に $7-t$ 個のかたまりを任意に並べれば条件を満たす順列が 1 つずつ得られるので
$$\left|\bigcap _{i\in T}{A}_i\right|=(7-t)!.$$
これは $T$ の選び方によらない。

包除原理. よって求める個数は
$$\sum _{t=0}^6(-1{)}^t(\genfrac{}{}{0ex}{}{6}{t})(7-t)!.$$
各項を計算すると
- $t=0$: $1\cdot 5040=5040$
- $t=1$: $6\cdot 720=4320$
- $t=2$: $15\cdot 120=1800$
- $t=3$: $20\cdot 24=480$
- $t=4$: $15\cdot 6=90$
- $t=5$: $6\cdot 2=12$
- $t=6$: $1\cdot 1=1$

であるから
$$5040-4320+1800-480+90-12+1=2119.$$

確認: 同じ方法で $1,2,3$ の場合は $3!-2\cdot 2!+1!=3$ となり、実際 $(1,3,2),(2,1,3),(3,2,1)$ の 3 個である。

隣り合う成分が $(i,i+1)$ となる箇所（「接続」）が 1 つもない順列の個数を求める。接続の入る位置の集合を $\{i,i+1\}$ の組 $i\in \{1,\dots ,6\}$ から選ぶ部分集合 $T$ の個数 $|T|=t$ に対し、それらを張り付けると $7-t$ 個のブロックの並べ方で $(7-t)!$ 通り。包除原理で ${\sum }_{t=0}^6(-1{)}^t(\genfrac{}{}{0ex}{}{6}{t})(7-t)!=5040-6\cdot 720+15\cdot 120-20\cdot 24+15\cdot 6-6\cdot 2+1=5040-4320+1800-480+90-12+1=2119$。検算: 既知の関係 $D_7+D_6=1854+265=2119$ に一致。