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

全体の個数

各位置に $4$ 種類のどれを置いてもよいので、重複順列により全体は $4^6=4096$ 個である。

条件の設定

$i=1,2,3,4$ に対し、$i$ 番目の文字（$\mathrm{A},\mathrm{B},\mathrm{C},\mathrm{D}$ の順）が一度も現れない文字列全体の集合を $A_i$ とする。求めるものは「どの文字も欠けていない」文字列の個数、すなわち $\left|\overline{A_1}\cap \overline{A_2}\cap \overline{A_3}\cap \overline{A_4}\right|$ である。

一般の包除原理より
$$\left|\overline{A_1}\cap \cdots \cap \overline{A_4}\right|=\sum _{k=0}^4(-1{)}^k\sum _{|I|=k}\left|\bigcap _{i\in I}{A}_i\right|.$$
ここで $|I|=0$ の項は全体の個数とする。

各項の計算

$|I|=k$ のとき、${\bigcap }_{i\in I}{A}_i$ は指定した $k$ 種類の文字をどれも使わない文字列、すなわち残りの $4-k$ 種類だけで作る長さ $6$ の文字列の集合なので
$$N_k=\left|\bigcap _{i\in I}{A}_i\right|=(4-k{)}^6$$
であり、$I$ の選び方によらない（条件が対称）。$|I|=k$ となる $I$ は $\left(\genfrac{}{}{0ex}{}{4}{k}\right)$ 通りあるから
$$\left|\overline{A_1}\cap \cdots \cap \overline{A_4}\right|=\sum _{k=0}^4(-1{)}^k(\genfrac{}{}{0ex}{}{4}{k})(4-k{)}^6.$$

計算

• $k=0$: $\left(\genfrac{}{}{0ex}{}{4}{0}\right)\cdot 4^6=4096$
• $k=1$: $\left(\genfrac{}{}{0ex}{}{4}{1}\right)\cdot 3^6=4\cdot 729=2916$
• $k=2$: $\left(\genfrac{}{}{0ex}{}{4}{2}\right)\cdot 2^6=6\cdot 64=384$
• $k=3$: $\left(\genfrac{}{}{0ex}{}{4}{3}\right)\cdot 1^6=4$
• $k=4$: $\left(\genfrac{}{}{0ex}{}{4}{4}\right)\cdot 0^6=0$

よって
$$4096-2916+384-4+0=1560.$$

答えは $1560$ 個である。

長さ6の文字列で4種類すべてが現れる個数は全射の個数 $4!S(6,4)$ に等しい。包除原理で計算する。
$4^6-\left(\genfrac{}{}{0ex}{}{4}{1}\right)3^6+\left(\genfrac{}{}{0ex}{}{4}{2}\right)2^6-\left(\genfrac{}{}{0ex}{}{4}{3}\right)1^6=4096-4\cdot 729+6\cdot 64-4=4096-2916+384-4=1560$。
検算：$S(6,4)=65$ なので $24\cdot 65=1560$。別の方法として、文字の個数の分布が (3,1,1,1) か (2,2,1,1) の場合を数える。(3,1,1,1) は $4\cdot \frac{6!}{3!}=4\cdot 120=480$。(2,2,1,1) は $\left(\genfrac{}{}{0ex}{}{4}{2}\right)\cdot \frac{6!}{2!2!}=6\cdot 180=1080$。合計 $1560$ で一致する。