Правило произведения · Размещения · Слова с ограничениями · ЕГЭ тип 8
Зачем нам комбинаторика в курсе информатики? Потому что именно она объясняет, почему энтропия Шеннона задаёт границу сжатия: мощность кодового пространства, число возможных сообщений и оптимальная длина кода — всё это комбинаторика.
Правило произведения: если первый шаг можно выполнить n₁ способами, второй — n₂ способами, …, k-й шаг — nₖ способами, и все выборы независимы, то число последовательностей:
| Задача | Расчёт | Ответ |
|---|---|---|
| Двузначный пароль из цифр 0–9 | 10 × 10 | 100 |
| 3-буквенное слово из {А,Б,В,Г}, с повторениями | 4 × 4 × 4 = 4³ | 64 |
| Двоичная строка длины 8 | 2⁸ | 256 |
| Рос. номер авто: 3 буквы (30) + 3 цифры | 30³ × 10³ | 27 000 000 |
Если каждую букву можно использовать не более одного раза, число k-буквенных слов из n различных букв:
На первой позиции n вариантов, на второй — (n−1) т.к. одна буква занята, и т.д.
A(5, 3) = 5 × 4 × 3 = 60 слов
| Тип ограничения | Формула | Пример (n=5, k=3) |
|---|---|---|
| Первая буква — конкретная «А» | 1 × n^(k−1) | 1 × 5² = 25 |
| Первая — из m гласных | m × n^(k−1) | 2 × 5² = 50 |
| Не содержит букву «Х» | (n−1)^k | 4³ = 64 |
| «Х» встречается ровно 1 раз | k × (n−1)^(k−1) | 3 × 4² = 48 |
| Без повторений | A(n,k) = n×(n−1)×… | 5×4×3 = 60 |
Условие: Сколько слов длины 5 из {А, Б, В, Г, Д} начинаются с «А» и не содержат повторений?
Условие: Сколько 4-значных чисел без цифры 0, в которых цифра 5 встречается ровно один раз?
Число слов длины k из алфавита мощности n — это nk. Чтобы закодировать одно слово, нужно log₂(nk) = k · log₂n бит — формула алфавитного подхода!
Если буквы встречаются с разными вероятностями, оптимальный код (Хаффман) не даёт каждой букве одинаковую длину — более редким нужно больше бит.
5 вопросов по комбинаторике · 20 XP за каждый правильный ответ