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

$1$ から $8$ の並べ方全体の集合を $U$ とし（$|U|=8!=40320$）、$i=1,2,\dots ,7$ に対して
$$A_i=\{\text{i のすぐ右隣に i+1 がある並べ方}\}$$
とおく。求める個数は $|U|-|A_1\cup \cdots \cup A_7|$ であり、包除原理より
$$|U\setminus (A_1\cup \cdots \cup A_7)|=\sum _{k=0}^7(-1{)}^k\sum _{|S|=k}|\bigcap _{i\in S}{A}_i|$$
である（$k=0$ の項は $|U|$）。

${\bigcap }_{i\in S}{A}_i$ の大きさ：$S\subset \{1,\dots ,7\}$, $|S|=k$ とする。$i\in S$ のとき「$i$ の直後に $i+1$」を要求する。たとえば $S$ が $1,2$ を含めば $1,2,3$ がこの順に連続することになり、要求された隣接はいくつかの連続した数のかたまり（ブロック）を作る。$k$ 個の隣接条件はそれぞれ $2$ つの単位を $1$ つにまとめるので、単位の個数は $8-k$ 個になる。ブロックの内部の順序は決まっているから、これら $8-k$ 個の単位を自由に並べればよく、
$$\left|\bigcap _{i\in S}{A}_i\right|=(8-k)!$$
となる。これは $S$ の選び方によらず、$S$ の選び方は $\left(\genfrac{}{}{0ex}{}{7}{k}\right)$ 通りある。

よって求める個数は
$$N=\sum _{k=0}^7(-1{)}^k(\genfrac{}{}{0ex}{}{7}{k})(8-k)!$$
である。各項を計算すると
- $k=0$：$1\cdot 40320=40320$
- $k=1$：$7\cdot 5040=35280$
- $k=2$：$21\cdot 720=15120$
- $k=3$：$35\cdot 120=4200$
- $k=4$：$35\cdot 24=840$
- $k=5$：$21\cdot 6=126$
- $k=6$：$7\cdot 2=14$
- $k=7$：$1\cdot 1=1$

したがって
$$N=40320-35280+15120-4200+840-126+14-1=16687$$
となる。

答え：$16687$ 通り

「$i$ のすぐ右隣に $i+1$ がある」ことを $i$ のところの「連続」と呼ぶ。包除原理を使う。

$A_i$ を「$i$ のすぐ右に $i+1$ がある並べ方の集合」とする。$7$ 個の条件 $A_1,\dots ,A_7$ のうち $k$ 個を選んで同時に成り立たせると、$i,i+1$ が連結されるので、ブロックの数は $8-k$ 個になる。これらの並べ方は $(8-k)!$ 通りで、選び方は $\left(\genfrac{}{}{0ex}{}{7}{k}\right)$ 通りである。

よって求める数は
${\sum }_{k=0}^7(-1{)}^k(\genfrac{}{}{0ex}{}{7}{k})(8-k)!$

各項は次のとおり。
- $k=0$: $40320$
- $k=1$: $7\cdot 5040=35280$
- $k=2$: $21\cdot 720=15120$
- $k=3$: $35\cdot 120=4200$
- $k=4$: $35\cdot 24=840$
- $k=5$: $21\cdot 6=126$
- $k=6$: $7\cdot 2=14$
- $k=7$: $1$

合計は $40320-35280+15120-4200+840-126+14-1=16687$。

検算として、連続を含まない順列の個数が満たす漸化式 $a_n=(n-1)a_{n-1}+(n-2)a_{n-2}$（$a_1=1,a_2=1$）を使う。$a_3=3,a_4=11,a_5=53,a_6=309,a_7=2119,a_8=7\cdot 2119+6\cdot 309=14833+1854=16687$ となり、一致する。