33. Слова, содержащие все буквы алфавита
Чтобы посчитать слова длины , содержащие все букв алфавита, проще посчитать противоположное: слова, в которых каких-то букв не хватает. «Не хватает буквы » — это свойство , и принцип включений и исключений даёт ответ .
Что пригодится из прошлого: включения и исключения через свойства — формула ; размещения с повторениями — слов длины в алфавите из букв ровно ; сочетания. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Задача
Задача. Найти количество слов длины в алфавите , которые содержат все буквы алфавита. Обозначим число таких слов .
Самый маленький случай: две буквы, три позиции
Алфавит , слова длины . Всего слов . Нужные нам слова содержат и , и ; «плохие» слова — те, где одной из букв нет: (нет ) и (нет ). Нужные слова: aab, aba, abb, baa, bab, bba. Их .
Тот же результат даёт формула: . Разберём, откуда она берётся.
Решение по формуле включений и исключений
Пусть — множество всех слов длины в алфавите . Тогда .
Свойство (): слово не содержит буквы . Нужные нам слова — те, у которых ни одно из свойств не выполнено (ни одной буквы не пропущено). Значит, .
Найдём числа . Фиксируем букв, которых в слове нет: . Слово составлено из оставшихся букв, повторять можно: таких слов . А выбрать, какие букв отсутствуют, можно способами. Поэтому
По принципу включений и исключений , то есть
Как читать. Начинаем со всех слов . Вычитаем слова без одной буквы (для каждой из букв — ). Но слова без двух букв мы вычли дважды: возвращаем , и так далее.
Разбор примера: ,
Сколько существует слов длины в алфавите , содержащих все три буквы?
| Слагаемое | |||
|---|---|---|---|
| 0 | 1 | 81 | +81 |
| 1 | 3 | 16 | −48 |
| 2 | 3 | 1 | +3 |
| 3 | 1 | 0 | 0 |
| сумма | 36 |
Ответ: .
Проверка другим способом. Слово длины с тремя разными буквами состоит из одной буквы, встретившейся дважды, и двух остальных по одному разу. Выбрать повторяющуюся букву можно способами, а слов с составом, например, — (напомним перестановки с повторяющимися элементами). Всего . Совпало.
Два замечательных частных случая
Случай . Слово длины , содержащее все букв, использует каждую ровно один раз — это перестановка. Значит, , и мы получили любопытное равенство
Например, для : .
Случай . В слове длины не поместятся все букв, поэтому , то есть
Для :
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 24 | 240 | 1560 |
Числа : нули при , затем при и дальше рост.
Другое прочтение. — это число способов раздать различных предметов получателям так, чтобы каждый получил хотя бы один: предмет — это позиция слова, а буква на ней — получатель.
Частые ошибки
- Вычитать только слова без одной буквы. Нужно продолжить: слова без двух букв, без трёх и так далее.
- Считать слова без букв как без коэффициента . Выбрать, какие букв пропущены, можно способами.
- Удивиться слагаемому . Оно равно при : слов вообще без всех букв нет. Его можно не писать.
- Применять формулу при ожидая положительного ответа. Результат всегда .
Проверь себя
1. Сколько слов длины в алфавите содержат обе буквы?
Решение
(все слова, кроме и ).
2. Сколько слов длины в алфавите содержат все три буквы?
Решение
.
3. Сколькими способами можно раздать различных подарков трём детям, чтобы каждому досталось хотя бы по одному?
Решение
Это то же число: подарок — позиция слова, ребёнок — буква. .
4. Проверьте по формуле, что .
Решение
.
Итог
- Слова, содержащие все буквы, — это слова без «пропущенных» букв: свойство — «нет буквы ».
- , поэтому .
- Если , получаем ; если , получаем .
- — число способов раздать различных предметов получателям так, чтобы каждый получил хотя бы один.
