Question

Введите первые девять цифр числа перестановок всех букв английского алфавита, которые не содержат в себе подстрок fish, rat или bird. Используйте принцип включений-исключений и рассуждения, похожие на те, которые мы проводили, когда получали общее количество перестановок.

Answer 1

— число перестановок, содержащих fish. B — число перестановок, содержащих rat. C — число перестановок, содержащих bird.
Всего число перестановок букв английского алфавита 26!.
Из этого числа надо вычесть число вхождений слова fish. Слово fish состоит из 4 букв, значит остаётся ещё 22 буквы алфавита. Итого, 23!.
Вычтем число вхождений слова rat: 24!.
Вычтем число вхождений слова bird: 23!.
Формула включений-исключений для нашего примера имеет вид
|A∪B∪C|=|A|+|B|+|C|−|A∩B|−|B∩C|−|A∩B∩C|.
Но так как fish и bird содержат общий символ i, то

|A∩C|=∅,
а так как bird и rat содержат общий символ r, то

|B∩C|=∅,
и значит

|A∩B∩C|=∅.
Тогда остаётся только

|A∪B∪C|=|A|+|B|+|C|−|A∩B|
Это число строк в которых содержится или слово fish , или слово rat, или слово bird, или они вместе (вместе могут быть только fish и rat). Так как нам надо вычислить количество перестановок, где эти строки не встречаются, то вычтем всё из общего числа перестановок и получим

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

Answer 2

Для решения этой задачи, давайте воспользуемся принципом включений-исключений. Первым шагом будет вычисление общего количества перестановок всех букв английского алфавита без каких-либо ограничений. Затем мы будем исключать перестановки, которые содержат подстроки fish, rat или bird.

1. Общее количество перестановок всех букв английского алфавита (9 символов): 9! = 362,880

2. Теперь рассмотрим перестановки, которые содержат подстроку "fish". Здесь есть 6 возможных позиций, где она может начинаться (первая, вторая, ..., шестая буква). Для каждого положения "fish" фиксировано 4 буквы, а оставшиеся 4 буквы могут переставляться между собой. Таким образом, количество перестановок с "fish" равно 6 * 4! = 144.

3. Теперь рассмотрим перестановки, которые содержат подстроку "rat". Аналогично, здесь есть 6 возможных позиций, где она может начинаться, и для каждого положения "rat" фиксировано 3 буквы, а оставшиеся 5 букв могут переставляться между собой. Количество перестановок с "rat" равно 6 * 3! = 36.

4. Теперь рассмотрим перестановки, которые содержат подстроку "bird". Здесь есть 7 возможных позиций, где она может начинаться, и для каждого положения "bird" фиксировано 4 буквы, а оставшиеся 5 букв могут переставляться между собой. Количество перестановок с "bird" равно 7 * 4! = 168.

5. Однако, если мы просто вычтем сумму перестановок с "fish", "rat" и "bird" из общего числа перестановок, мы дважды учтем перестановки, которые содержат две из указанных подстрок. Поэтому нужно добавить обратно такие перестановки.

6. Рассмотрим перестановки, которые содержат одновременно подстроки "fish" и "rat". Здесь есть 5 возможных позиций для "fish" и 4 возможных позиции для "rat", и для каждой комбинации фиксировано 2 буквы. Оставшиеся 3 буквы могут переставляться между собой. Количество перестановок с "fish" и "rat" равно 5 * 4 * 2! = 40.

7. Рассмотрим перестановки, которые содержат одновременно подстроки "fish" и "bird". Здесь есть 4 возможных позиции для "fish" и 5 возможных позиций для "bird", и для каждой комбинации фиксировано 3 буквы. Оставшиеся 2 буквы могут переставляться между собой. Количество перестановок с "fish" и "bird" равно 4 * 5 * 2! = 40.

8. Рассмотрим перестановки, которые содержат одновременно подстроки "rat" и "bird". Здесь есть 5 возможных позиций для "rat" и 4 возможных позиции для "bird", и для каждой комбинации фиксировано 2 буквы. Оставшиеся 3 буквы могут переставляться между собой. Количество перестановок с "rat" и "bird" равно 5 * 4 * 2! = 40.

9. И, наконец, рассмотрим перестановки, которые содержат все три подстроки "fish", "rat" и "bird". Здесь есть 4 возможных позиции для "fish", 3 возможных позиции для "rat" и 4 возможных позиции для "bird", и для каждой комбинации фиксировано 1 буква. Оставшиеся 1 буква может быть только одной. Количество перестановок с "fish", "rat" и "bird" равно 4 * 3 * 4 * 1 = 48.

Теперь мы можем применить принцип включений-исключений:

Количество перестановок без "fish", "rat" и "bird" = Общее количество перестановок - (Перестановки с "fish") - (Перестановки с "rat") - (Перестановки с "bird") + (Перестановки с "fish" и "rat") + (Перестановки с "fish" и "bird") + (Перестановки с "rat" и "bird") - (Перестановки с "fish", "rat" и "bird")

Количество перестановок без "fish", "rat" и "bird" = 362,880 - 144 - 36 - 168 + 40 + 40 + 40 - 48

Количество перестановок без "fish", "rat" и "bird" = 362,184

Таким образом, первые девять цифр числа перестановок всех букв английского алфавита, которые не содержат в себе подстрок fish, rat или bird, равны