Подтема 2 из 6
Сколько раз встречается буква
Как посчитать слова, где буква встречается ровно, хотя бы или не более нужного числа раз.
Места для буквы
Сколько пятибуквенных слов из Т, О, Р, К, А содержат ровно две буквы О?
«Ровно k одинаковых букв» — два действия: выбрать места для этой буквы и заполнить остальные места другими буквами.
Два места из пяти можно выбрать 10 способами: порядок выбора мест не важен — «места 1 и 3» и «места 3 и 1» дают одно слово.
Остальные три места заполняют любыми буквами, кроме О, — по 4 варианта. Всего 10 · 4³ = 640 слов.
Тонкости:число сочетаний
Число способов выбрать k мест из n обозначают Cₙᵏ: выбрать места по очереди n · (n − 1) · … · (n − k + 1) способами и разделить на k! — столько порядков у каждого набора. C₅² = 5 · 4 / 2 = 10, C₆³ = 6 · 5 · 4 / 6 = 20. Слов с ровно k данными буквами — Cₙᵏ · (m − 1)ⁿ⁻ᵏ.
Разбор случаев
Если ограничение на место мешает одной формуле, слова делят на случаи и складывают. Добавим условие задачи темы: слово не начинается с А.
- Первая буква —
О: вторую О ставим на одно из 4 оставшихся мест, ещё три места — из К, Р, Т, А: 4 · 4³ = 256. - Первая буква — К, Р или Т: 3 варианта, две О — на 2 из 4 оставшихся мест (6 способов), ещё два места — по 4 варианта: 3 · 6 · 4² = 288.
Всего 256 + 288 = 544 слова.
«Хотя бы» и «не более»
«Хотя бы» и «не более» переводят в точные количества. Выбери формулировку, чтобы увидеть, сколько раз буква может встретиться:
- ровно 2
- 2
- не более 2
- 0, 1, 2
- не менее 2
- 2, 3, 4, …
- хотя бы одна
- 1, 2, 3, …
- ни одной
- 0
«Хотя бы одну» короче считать через дополнение: из всех слов вычесть слова совсем без этой буквы. Слов хотя бы с одной О: 5⁵ − 4⁵ = 3125 − 1024 = 2101.
Тонкости:две обязательные буквы
Если нужны и А, и Б, вычитают слова без А и слова без Б, но слова без обеих букв вычтены дважды — их возвращают один раз. Для пятибуквенных слов из АБВГ: 4⁵ − 3⁵ − 3⁵ + 2⁵ = 570.
Проверки в программе
Каждая фраза условия — отдельная проверка в программе.
| В условии | Проверка |
|---|---|
| ровно две О | word.count('О') == 2 |
| не менее двух О | word.count('О') >= 2 |
| хотя бы одна О | 'О' in word |
| нет буквы О | 'О' not in word |
| не начинается с А | word[0] != 'А' |
| заканчивается гласной | word[-1] in 'АО' |
Проверки соединяют . Для задачи темы на этом шаге:
from itertools import product count = 0for letters in product('АКОРТ', repeat=5): word = ''.join(letters) if word.count('О') == 2 and word[0] != 'А': count += 1print(count)Программа подтвердила разбор случаев: 544. word.count('АО') считает фрагменты АО подряд, а не отдельные А и О: число гласных — это word.count('А') + word.count('О').
Перестановки с повторами
Если переставляют все буквы слова с одинаковыми буквами, одинаковые буквы нельзя считать разными. У слова ТОПОТ пять букв, но две Т и две О одинаковы. Если подписать их как разные, получится 5! = 120 расстановок, и каждое настоящее слово посчитано 2! · 2! = 4 раза.
В программе permutations считает одинаковые буквы разными, и дубликаты убирает :
from itertools import permutations print(len(list(permutations('ТОПОТ'))))print(len(set(permutations('ТОПОТ'))))Итого
- Ровно kместа для буквы, остальные — другими буквами
- Разбор случаевпо первой букве, затем сложить
- Хотя бы однавсе минус без этой буквы
- Проверки
count,in,word[0] - Повторы буквn! / (a! · b! · …)
Проверьте себя
Ответь сначала сам, потом открой ответ.
АБВГ содержат ровно две А?ОтветСкрыть ответ
ОтветСкрыть ответ
А — и в слове было бы больше двух.АБВ содержат хотя бы одну А?ОтветСкрыть ответ
ОтветСкрыть ответ
word.count('АБ') == 1 не подходит для условия «в слове одна А и одна Б»?ОтветСкрыть ответ
count('АБ') ищет фрагмент АБ подряд: в слове БГА одна А и одна Б, а фрагмента нет. Нужно word.count('А') == 1 and word.count('Б') == 1.Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Ровно две А
Сколько пятибуквенных слов из АБВГД содержит ровно две А? Повторения разрешены.
Введите число.
Подсказка
Места для А без порядка, остальные — из четырёх букв.
Решение
Два места для А из пяти можно выбрать 10 способами, остальные три места — любыми из четырёх других букв: 10 · 4³ = 640.
Решение программой
from itertools import product count = 0for letters in product('АБВГД', repeat=5): word = ''.join(letters) if word.count('А') == 2: count += 1print(count)Ответ: 640
Ровно три гласные
Сколько пятибуквенных слов из АОБВГ содержит ровно три гласные?
Введите число.
Подсказка
Выбор мест гласных и выбор самих гласных.
Решение
Три места для гласных из пяти — 10 способов, на каждом — А или О (2³), на остальных двух — согласные (3²): 10 · 8 · 9 = 720.
Решение программой
from itertools import product count = 0for letters in product('АОБВГ', repeat=5): word = ''.join(letters) if sum(c in 'АО' for c in word) == 3: count += 1print(count)Ответ: 720
Слова Васи
Вася составляет 6-буквенные слова из букв К, О, Р, А, Л. Буква К должна встречаться ровно два раза, остальные буквы — любое количество раз или не встречаться совсем. Слово не может начинаться с буквы А. Сколько слов может составить Вася?
Введите число.
Подсказка
Разбери случаи по первой букве.
Решение
Если первая буква К, вторая К стоит на одном из пяти мест, остальные четыре — из О, Р, А, Л: 5 · 4⁴ = 1280. Если первая — О, Р или Л, две К ставят на 2 из 5 оставшихся мест (10 способов), ещё три места — по 4 варианта: 3 · 10 · 4³ = 1920. Всего 3200.
Решение программой
from itertools import product count = 0for letters in product('КОРАЛ', repeat=6): word = ''.join(letters) if word.count('К') == 2 and word[0] != 'А': count += 1print(count)Ответ: 3200
Коды Светы
Света составляет 5-буквенные коды из букв П, А, Р, У, С. Каждую букву можно использовать любое количество раз, при этом в коде должно быть не менее двух гласных, а последней буквой не может быть С. Сколько различных кодов может составить Света?
Введите число.
Подсказка
Разбери случаи по последней букве.
Решение
Если последняя буква — гласная А или У, среди первых четырёх нужна хотя бы одна гласная: 2 · (5⁴ − 3⁴) = 1088. Если последняя — П или Р, среди первых четырёх нужно не менее двух гласных: 2 · (5⁴ − 3⁴ − 4 · 2 · 3³) = 656. Всего 1088 + 656 = 1744.
Решение программой
from itertools import product count = 0for letters in product('ПАРУС', repeat=5): word = ''.join(letters) if sum(c in 'АУ' for c in word) >= 2 and word[-1] != 'С': count += 1print(count)Ответ: 1744
Хотя бы одна Б
Сколько пятибуквенных слов из АБВ содержит хотя бы одну Б? Повторения разрешены.
Введите число.
Подсказка
Из всех слов вычти слова без Б.
Решение
Всего слов 3⁵ = 243, без Б — 2⁵ = 32. Хотя бы одна Б есть в 243 − 32 = 211 словах.
Решение программой
from itertools import product count = 0for letters in product('АБВ', repeat=5): word = ''.join(letters) if 'Б' in word: count += 1print(count)Ответ: 211
Не более одной А
Сколько четырёхбуквенных слов из АБВГ содержит не более одной А?
Введите число.
Подсказка
«Не более одной» — ноль или одна.
Решение
Слов без А — 3⁴ = 81, с одной А — 4 места · 3³ = 108. Всего 81 + 108 = 189.
Решение программой
from itertools import product count = 0for letters in product('АБВГ', repeat=4): word = ''.join(letters) if word.count('А') <= 1: count += 1print(count)Ответ: 189
И А, и Д
Сколько четырёхбуквенных слов из АБВГД содержит и А, и Д?
Введите число.
Подсказка
При вычитании учти слова, где нет обеих букв.
Решение
Из всех 5⁴ = 625 слов вычитаем слова без А (4⁴ = 256) и слова без Д (ещё 256). Слова без обеих букв вычтены дважды — возвращаем их 3⁴ = 81: 625 − 256 − 256 + 81 = 194.
Решение программой
from itertools import product count = 0for letters in product('АБВГД', repeat=4): word = ''.join(letters) if 'А' in word and 'Д' in word: count += 1print(count)Ответ: 194
Перестановки слова АНАНАС
Сколько различных слов получается перестановкой всех букв слова АНАНАС?
Введите число.
Подсказка
Одинаковые буквы нельзя считать различными.
Решение
В слове АНАНАС три А и две Н. Если считать все буквы разными, перестановок 6! = 720, и каждое слово посчитано 3! · 2! = 12 раз: 720 / 12 = 60.
Решение программой
from itertools import permutations print(len(set(permutations('АНАНАС'))))Ответ: 60
Перестановки слова КОЛОКОЛ
Сколько различных кодов можно составить перестановкой всех букв слова КОЛОКОЛ?
Введите число.
Подсказка
Две К, три О, две Л.
Решение
В слове КОЛОКОЛ две К, три О и две Л. Перестановок 7! / (2! · 3! · 2!) = 5040 / 24 = 210.
Решение программой
from itertools import permutations print(len(set(permutations('КОЛОКОЛ'))))Ответ: 210