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

全体の個数

各位置に 4 種類の文字のどれでも置けるので、重複順列より文字列は全部で $4^6=4096$ 通りある。

条件の設定

文字 $a,b,c,d$ をそれぞれ 1 番目〜4 番目の文字とし、
$$A_i=\{i\text{ 番目の文字が 1 回も現れない文字列}\}(i=1,2,3,4)$$
とおく。求めるのは、どの文字も「現れない」ことがない文字列の個数、すなわち $\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|$$
を使う。ただし $k=0$ の項は全体の個数 $4^6$ とする。

$N_k$ の計算

$k$ 個の文字を指定して、それらがすべて現れない文字列は、残りの $4-k$ 種類の文字だけで長さ 6 の文字列をつくるので $(4-k{)}^6$ 通りある。これはどの $k$ 個を選んでも同じ（条件が対称）なので、$N_k=(4-k{)}^6$ である。$k$ 個の選び方は $\left(\genfrac{}{}{0ex}{}{4}{k}\right)$ 通りだから、
$$\sum _{k=0}^4(-1{)}^k(\genfrac{}{}{0ex}{}{4}{k})(4-k{)}^6$$
を計算すればよい。

計算

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

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

答えは $1560$ 通りである。

長さ 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-2916+384-4=1560$。

検算：第二種スターリング数 $S(6,4)=65$ なので、$4!\times 65=24\times 65=1560$。

もう一つの検算：出現回数の型は (3,1,1,1) と (2,2,1,1) の 2 通り。(3,1,1,1) は文字の選び方 4 通り、並べ方 $6!/3!=120$ 通りで $480$。(2,2,1,1) は 2 回現れる文字の選び方 $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ 通り、並べ方 $6!/(2!2!)=180$ 通りで $1080$。合計 $480+1080=1560$ で一致する。