Senior Pimiento

fish, rat or bird

Задача:

Вычислить число перестановок всех букв английского алфавита, которые не содержат в себе подстрок fish, rat или bird.

Решение:

1.  **A** — число перестановок, содержащих **fish**. **B** — число перестановок, содержащих **rat**. **C** — число перестановок, содержащих **bird**.
2.  Всего число перестановок букв английского алфавита **26!**.
3.  Из этого числа надо вычесть число вхождений слова **fish**. Слово **fish** состоит из 4 букв, значит остаётся ещё 22 буквы алфавита. Итого, **23!**.
4.  Вычтем число вхождений слова **rat**: **24!**.
5.  Вычтем число вхождений слова **bird**: **23!**.
6.  Формула включений-исключений для нашего примера имеет вид

  |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| - |A ∩ B ∩ C|.

Но так как **fish** и **bird** содержат общий символ **i**, то

  |A ∩ C| = ⌀,

а так как **bird** и **rat** содержат общий символ **r**, то

  |B ∩ C| = ⌀,

и значит

  |A ∩ B ∩ C| = \empty.

Тогда остаётся только

  |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B|

Это число строк в которых содержится или слово **fish** , или слово **rat**, или слово **bird**, или они вместе (вместе могут быть только **fish** и **rat**). Так как нам надо вычислить количество перестановок, где эти строки не встречаются, то вычтем всё из общего числа перестановок и получим

  26! - |A| + |B| + |C| - |A ∩ B| = 26! - 23! - 24! - 23! + 21!.