fish, rat, bird
Table of Contents
1 Задача:
Вычислить число перестановок всех букв английского алфавита, которые не содержат в себе подстрок fish, rat или bird.
2 Решение:
- \(A\) — число перестановок, содержащих fish. \(B\) — число перестановок, содержащих rat. \(C\) — число перестановок, содержащих bird.
- Всего число перестановок букв английского алфавита 26!.
- Из этого числа надо вычесть число вхождений слова fish. Слово fish состоит из 4 букв, значит остаётся ещё 22 буквы алфавита. Итого, 23!.
- Вычтем число вхождений слова rat: 24!.
- Вычтем число вхождений слова bird: 23!.
- Формула включений-исключений для нашего примера имеет вид
\begin{equation*}
|A \cup{} B \cup C| = |A| + |B| + |C| - |A \cap{} B| - |B \cap{} C| - |A \cap B \cap C|.
\end{equation*}
Но так как fish и bird содержат общий символ i, то
\begin{equation*}
|A \cap C| = \emptyset{},
\end{equation*}
а так как bird и rat содержат общий символ r, то
\begin{equation*}
|B \cap C| = \emptyset{},
\end{equation*}
и значит
\begin{equation*}
|A \cap B \cap C| = \emptyset{}.
\end{equation*}
Тогда остаётся только
\begin{equation*}
|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B|
\end{equation*}
Это число строк в которых содержится или слово fish , или слово rat, или слово bird, или они вместе (вместе могут быть только fish и rat). Так как нам надо вычислить количество перестановок, где эти строки не встречаются, то вычтем всё из общего числа перестановок и получим
\begin{equation*}
26! - |A| + |B| + |C| - |A \cap B| = 26! - 23! - 24! - 23! + 21!.
\end{equation*}