Комбинаторика слов

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 27 · страница 27.4
Комбинаторика слов
Правило произведения · Размещения · Слова с ограничениями · ЕГЭ тип 8
Зачем нам комбинаторика в курсе информатики?
Потому что именно она объясняет, почему энтропия Шеннона задаёт границу сжатия: мощность кодового пространства, число возможных сообщений и оптимальная длина кода — всё это комбинаторика.
ФГОС
ФОП
ЕГЭ №8
ЕГЭ №11
Связь с предыдущей темой.
Число возможных двоичных слов длины n равно 2
n
. Именно поэтому для кодирования N символов нужно не менее log₂N бит — это и есть формула Хартли.
01
Правило произведения
Правило произведения:
если первый шаг можно выполнить n₁ способами, второй — n₂ способами, …, k-й шаг — nₖ способами, и все выборы
независимы
, то число последовательностей:
N = n₁ × n₂ × … × nₖ
Разбор примеров
Задача
Расчёт
Ответ
Двузначный пароль из цифр 0–9
10 × 10
100
3-буквенное слово из {А,Б,В,Г}, с повторениями
4 × 4 × 4 = 4³
64
Двоичная строка длины 8
2⁸
256
Рос. номер авто: 3 буквы (30) + 3 цифры
30³ × 10³
27 000 000
02
Размещения без повторений
Если каждую букву можно использовать
не более одного раза
, число k-буквенных слов из n различных букв:
A(n, k) = n × (n−1) × (n−2) × … × (n−k+1)
На первой позиции n вариантов, на второй — (n−1) т.к. одна буква занята, и т.д.
Пример: 3-буквенные слова без повторений из {А,Б,В,Г,Д}
A(5, 3) = 5 × 4 × 3 =
60 слов
Сравнение.
С повторениями: 5³ = 125. Без повторений: A(5,3) = 60. Запрет повторений уменьшает число вариантов вдвое!
03
Типы задач ЕГЭ: ограничения
Тип ограничения
Формула
Пример (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
04
Разбор задачи ЕГЭ шаг за шагом
Задача ЕГЭ тип 8
Условие:
Сколько слов длины 5 из {А, Б, В, Г, Д} начинаются с «А» и не содержат повторений?
Позиция 1:
только «А» →
1
вариант
Позиция 2:
любая из оставшихся 4 букв →
4
варианта
Позиция 3:
любая из оставшихся 3 букв →
3
варианта
Позиция 4:
из оставшихся 2 →
2
варианта
Позиция 5:
последняя буква →
1
вариант
Итого: 1 × 4 × 3 × 2 × 1 = 24 слова
Задача 2: цифра 5 ровно один раз
Условие:
Сколько 4-значных чисел без цифры 0, в которых цифра 5 встречается ровно один раз?
Шаг 1:
выбрать позицию для «5» →
4
варианта (любая из 4 позиций)
Шаг 2:
остальные 3 позиции — цифры 1–9, кроме 5 =
8
вариантов каждая → 8³ = 512
Итого: 4 × 8³ = 4 × 512 = 2 048 чисел
05
Визуальный конструктор слов
🔤
Составь слово — правило произведения в действии
Алфавит
Длина слова
Повторения
06
Тренажёр ЕГЭ: задачи с ограничениями
🎲
ЕГЭ тип 8 — пошаговый разбор
Нажми «Новая задача» для начала
07
Связь с информацией и энтропией
Число слов длины k из алфавита мощности n — это
n
k
. Чтобы закодировать одно слово, нужно log₂(n
k
) =
k · log₂n бит
— формула алфавитного подхода!
Число слов = nᵏ → I = log₂(nᵏ) = k · log₂n бит
Если буквы встречаются с разными вероятностями, оптимальный код (Хаффман) не даёт каждой букве одинаковую длину — более редким нужно больше бит.
Энтропия как нижняя граница.
H(p₁,…,pₙ) ≤ log₂n. Равенство — при равных вероятностях.
Интерактив: алфавит размера n → информация на слово
Размер алфавита n =
4
Длина слова k =
3
Число слов nᵏ
64
Бит на слово
6.00
log₂n (на букву)
2.00
🎯
Мини-тест: 5 вопросов
XP: 0
🧩
Проверь себя
5 вопросов по комбинаторике · 20 XP за каждый правильный ответ