Комбинаторика: от базовых приёмов к вероятностным моделям

Базовые принципы счёта и простые задачи

Комбинаторика отвечает на вопрос: сколько существует вариантов выбрать, упорядочить или распределить объекты при заданных правилах. Эти навыки — фундамент для вероятностных моделей: вероятность часто равна отношению числа благоприятных исходов к числу всех исходов.

В этой статье мы разберём самые важные принципы счёта и научимся решать типовые простые задачи.

Что именно мы считаем

Обычно мы считаем количество исходов (вариантов), которые удовлетворяют условиям.

Важно заранее уточнить два вопроса:

Важен ли порядок? (например, пароль AB отличается от BA, а набор {A,B} — нет)

Разрешены ли повторения? (можно ли выбрать один и тот же объект несколько раз)

Правило сложения

Правило сложения: если действие можно выполнить одним из нескольких взаимоисключающих способов, то общее число способов — это сумма.

Пример: в меню есть 3 вида супа и 5 видов салата. Сколько способов выбрать одно блюдо, если берём либо суп, либо салат?

Ответ: .

Ключевое слово — либо. Способы не пересекаются.

Правило умножения

Правило умножения: если действие выполняется в несколько последовательных шагов, и на каждом шаге есть фиксированное число вариантов, то общее число вариантов — произведение.

Пример: составляем код из 2 символов: сначала буква (4 варианта), потом цифра (10 вариантов). Сколько кодов?

Ответ: .

!Дерево вариантов показывает, почему при последовательных шагах количества перемножаются

Частая ошибка

Если варианты на шагах зависят от предыдущего выбора, правило умножения всё равно работает, но множители могут быть разными.

Пример: из 5 разных книг выбираем 2 в порядке выдачи: первую — 5 способов, вторую — 4 (первую уже нельзя повторить). Итого .

Факториал как удобная запись

Факториал числа обозначают как и читают эн факториал.

Определение:

Здесь:

— число объектов

знак означает умножение

многоточие означает продолжение по той же схеме

По договорённости (это полезно для формул и корректных краевых случаев).

Перестановки

Перестановка — это упорядочивание всех разных объектов.

Число перестановок различных объектов равно .

Пример: сколькими способами можно рассадить 4 разных человека по 4 стульям в ряд?

на первый стул: 4 варианта

на второй: 3

на третий: 2

на четвёртый: 1

Итого .

Размещения (упорядоченный выбор)

Размещение без повторений: выбираем объектов из в порядке, не повторяя.

Обозначение: .

Формула:

Где:

— сколько объектов доступно всего

— сколько выбираем

— факториал числа

дробь означает деление: мы “убираем” множители, которые не участвуют в первых позициях

Пример: 5 разных книг на полке. Сколькими способами выбрать 2 книги в порядке: первая, затем вторая?

(Это то же самое, что по правилу умножения.)

Сочетания (неупорядоченный выбор)

Сочетание без повторений: выбираем объектов из без учёта порядка.

Обозначения: или .

Формула:

Где:

— всего объектов

— сколько выбираем

— учитывает, что один и тот же набор можно упорядочить способами, но нам порядок не важен

Пример: из 5 разных книг выбрать 2 просто взять две, порядок не важен.

Связь размещений и сочетаний

Для выбора разных объектов из :

если порядок важен:

если порядок не важен:

Они связаны так:

Смысл: сначала выбираем набор (), затем упорядочиваем выбранные объектов ().

Дополнение (удобный обходной путь)

Иногда проще посчитать не то, что нужно, а противоположное событие, а затем вычесть.

Если всего исходов, а “плохих” , то “хороших” .

Пример: сколько двузначных чисел (от 10 до 99) не содержат цифру 7?

всего двузначных чисел: 90

посчитаем напрямую без 7 через правило умножения:

- десятки: 8 вариантов (1–9, кроме 7) - единицы: 9 вариантов (0–9, кроме 7) - итого

Ответ: 72.

(Заметьте: здесь прямой подсчёт оказался простым; но в более сложных задачах дополнение часто делает решение короче.)

Сложение с пересечением: принцип включения–исключения для двух множеств

Если способы не взаимоисключающие, при сложении возникает двойной счёт. Исправляет это формула для двух множеств.

Пусть:

— множество исходов типа “A”

— множество исходов типа “B”

— исходы, которые принадлежат хотя бы одному из множеств (A или B)

— исходы, которые принадлежат обоим (A и B)

— количество элементов в (мощность множества)

Тогда:

Почему минус? Элементы из пересечения мы при сложении посчитали дважды.

Пример: в группе 18 человек изучают английский, 12 — немецкий, 5 — оба языка. Сколько изучают хотя бы один язык?

!Диаграмма Венна показывает, как пересечение учитывается при подсчёте

Краткая памятка формул

| Ситуация | Порядок важен | Повторения | Сколько способов | |---|---:|---:|---| | Выбрать 1 из взаимоисключающих вариантов | нет | зависит | сумма | | Последовательные шаги | зависит | зависит | произведение | | Упорядочить все разных объектов | да | нет | | | Выбрать и упорядочить из | да | нет | | | Выбрать из без порядка | нет | нет | | | “A или B” с пересечением | нет | — | |

Как это подготовит нас к вероятностям

В теории вероятностей (в классической модели) часто используют идею:

все элементарные исходы считаются равновозможными

вероятность события = доля исходов, ведущих к событию

То есть нам почти всегда нужно уметь считать:

общее число исходов

число исходов, удовлетворяющих условию

В следующих материалах мы будем развивать эти методы и научимся уверенно считать в задачах на вероятность, в том числе там, где без комбинаторики не обойтись.

Перестановки, размещения, сочетания и их вариации

В прошлой статье мы научились считать варианты с помощью правил сложения и умножения, а также познакомились с факториалом, перестановками, размещениями и сочетаниями без повторений. Теперь систематизируем эти объекты и добавим важные вариации: повторения, одинаковые элементы, круговые перестановки и “выбор с возвращением”. Это напрямую понадобится в вероятностных моделях, где нужно корректно посчитать число равновозможных исходов.

Как быстро выбрать правильную модель

Почти любая задача на подсчёт сводится к ответам на два вопроса:

Важен ли порядок?

Разрешены ли повторения?

!Дерево решений: какой тип подсчёта выбрать

Дальше мы разберём каждый случай и типовые формулы.

Перестановки

Перестановки без повторений

Перестановка — это упорядочивание всех различных объектов.

Число перестановок:

Где:

— число перестановок (часто пишут и просто )

— сколько объектов мы переставляем

— произведение

Смысл: на первое место можно поставить объектов, на второе — (один уже занят), и так далее.

Перестановки с повторяющимися элементами

Иногда элементы не все различны: например, буквы в слове или шары двух цветов.

Пусть всего элементов, но среди них есть группы одинаковых:

одинаковых элементов первого типа

одинаковых элементов второго типа

...

одинаковых элементов -го типа

При этом .

Число различных перестановок:

Что означает каждая часть:

— как если бы все элементов были различны

деление на исправляет “двойной счёт”: перестановки одинаковых элементов внутри своей группы не создают новых вариантов

Пример: сколько различных перестановок букв в слове “LEVEL” (5 букв, из них L — 2 раза, E — 2 раза, V — 1 раз)?

Размещения

Размещение — это упорядоченный выбор: мы выбираем позиций (мест) и заполняем их элементами.

Размещения без повторений

Из различных объектов выбираем в определённом порядке.

Расшифровка:

— число размещений

— сколько объектов доступно

— сколько выбираем (и упорядочиваем)

“убирает хвост” произведения в , оставляя ровно множителей:

Пример: сколько способов выбрать председателя и секретаря из 10 человек?

роли различны, значит порядок важен

повторять человека нельзя

Размещения с повторениями

Если повторения разрешены (например, код, пароль, выбор “с возвращением”), то на каждую из позиций есть вариантов.

Где:

— размещения с повторениями (часто надчеркивание используют как напоминание “с повторениями”)

— число вариантов на каждом шаге

— длина последовательности

— результат применения правила умножения: ( раз)

Пример: сколько PIN-кодов длины 4 из цифр 0–9 (повторы разрешены)?

Сочетания

Сочетание — это неупорядоченный выбор: важен набор, а не порядок.

Сочетания без повторений

Пояснение:

или — число сочетаний

— как если бы выбирали и упорядочивали

деление на убирает “лишние” перестановки внутри выбранного набора (они не должны отличаться)

деление на убирает объекты, которые не попали в выбор

Пример: сколько способов выбрать 3 книги из 12 (порядок не важен)?

Сочетания с повторениями

Если мы выбираем объектов из типов, и один тип можно взять несколько раз (например, 3 пирожных из 5 видов), это сочетания с повторениями.

Формула:

Как читать параметры:

— число типов (категорий)

— сколько всего предметов выбираем

появляется из классической модели “звёзды и перегородки” (известна как метод stars and bars)

Пример: сколькими способами можно выбрать 4 шарика мороженого, если есть 3 вкуса, и можно брать один вкус многократно?

Полезные связи и частые ловушки

Связь размещений и сочетаний

Если выбрать различных элементов из без порядка, а потом упорядочить выбранные, получатся размещения:

Здесь:

— выбираем набор

— переставляем выбранные элементов всеми способами

Круговые перестановки

Если мы расставляем людей по кругу, то поворот круга не меняет рассадку: “все сдвинулись на один стул” — тот же вариант.

Для различных объектов число круговых перестановок:

Почему так: зафиксируем одного человека “в качестве начала отсчёта”, а остальных рассадим в ряд вокруг него — это .

Важно: если отражение (по часовой и против часовой стрелки) тоже считается одинаковым, задача уже другая, и формула меняется.

Таблица-резюме

| Объект | Порядок важен | Повторения | Формула | |---|---:|---:|---| | Перестановки | да | нет | | | Перестановки с одинаковыми элементами | да | да (из-за одинаковости) | | | Размещения | да | нет | | | Размещения с повторениями | да | да | | | Сочетания | нет | нет | | | Сочетания с повторениями | нет | да | |

Почему это важно для вероятностей

В классической вероятности часто используют идею:

Ошибки в вероятностях почти всегда начинаются с неверного выбора модели подсчёта:

перепутали порядок (сочетания вместо размещений или наоборот)

забыли про повторения

не учли одинаковые элементы

не заметили, что “по кругу” повороты не различаются

Если уверенно отличать эти случаи, большинство задач на вероятность становятся технически простыми: остаётся аккуратно посчитать числитель и знаменатель.

Дополнительные источники

Факториал

Размещения, перестановки, сочетания

Метод «звёзды и перегородки»

Биномиальные коэффициенты и формула бинома Ньютона

В предыдущих статьях мы научились отличать ситуации, где важен порядок, и где он не важен, а также считать сочетания . В этой статье мы сделаем следующий важный шаг: посмотрим на как на биномиальные коэффициенты и научимся применять формулу бинома Ньютона для раскрытия степеней вида . Это напрямую связывает комбинаторику с вероятностными моделями (например, со схемой независимых испытаний).

Биномиальные коэффициенты

Биномиальный коэффициент — это число способов выбрать элементов из различных элементов без учёта порядка.

Его обозначают так:

-

(читают: эн по ка)

Эти записи равны:

Формула через факториалы

Если и — целые числа, причём , то

Разберём, что означает каждая часть:

— сколько всего различных объектов.

— сколько объектов выбираем.

— число перестановок всех объектов, то есть количество способов упорядочить их.

— число способов упорядочить те объекты, которые не попали в выбор.

— число способов упорядочить выбранные объектов. Мы делим на , потому что в сочетаниях порядок не важен.

Эта формула продолжает идею из прошлых тем: сначала мысленно считаем упорядоченные варианты, а затем делением убираем лишний счёт из-за порядка.

Базовые свойства биномиальных коэффициентов

Граничные значения

Почему это разумно:

означает: выбрать “ничего” можно ровно одним способом.

означает: выбрать “всё” можно ровно одним способом.

Симметрия

Смысл: выбрать элементов равносильно выбрать элементов, которые останутся.

Пример: число способов выбрать 2 человека из 10 равно числу способов “не выбрать” 8 человек из 10.

Правило Паскаля

Комбинаторное объяснение:

Рассмотрим элементов и выделим среди них один “особый”. Все наборы из элементов делятся на два непересекающихся типа:

наборы, где “особого” элемента нет: их

наборы, где “особый” элемент есть: тогда остальные выбираем из оставшихся , то есть

Сумма и даёт общее число наборов .

Треугольник Паскаля

Треугольник Паскаля — это таблица, в которой стоят числа . Он удобен для быстрого получения коэффициентов и наглядно показывает правило Паскаля.

!Наглядное построение биномиальных коэффициентов по правилу Паскаля

Формула бинома Ньютона

Теперь главный результат: как раскрывать .

Формулировка

Для целого верно:

Объясним, что означает каждый элемент формулы:

— это произведение одинаковых скобок:

означает: мы складываем выражения для всех от до .

— сколько раз мы “выбрали” при раскрытии скобок.

Тогда — сколько раз мы “выбрали” .

— вид слагаемого, если ровно раз взяли , а остальные разы .

— сколько разных способов получить именно при перемножении: это число способов выбрать, в каких из скобок мы берём (а в остальных берём ).

Именно здесь комбинаторика “прошивает” алгебру: коэффициенты появляются как количество способов выбора.

Маленькие примеры

Для :

Здесь:

соответствует выбору “ноль раз взять ”

соответствует двум вариантам: взять из первой скобки или из второй

соответствует выбору “два раза взять ”

Для :

Коэффициенты — это строка треугольника Паскаля для .

Важное следствие: сумма биномиальных коэффициентов

Если в формуле бинома Ньютона положить и , получим:

Левая часть равна , значит:

Комбинаторный смысл тоже простой: — число всех подмножеств -элементного множества. При этом подмножеств размера ровно , и если сложить по всем , получим общее количество подмножеств.

Как это переходит в вероятности

В вероятностях очень часто встречается ситуация: есть независимых испытаний, в каждом “успех” происходит с вероятностью , а “неуспех” — с вероятностью . Это называют схемой Бернулли.

Вероятность ровно успехов равна:

Почему так устроено:

отвечает за вероятности тех испытаний, где случился успех (их штук)

отвечает за неуспехи (их )

считает, сколькими способами можно выбрать, в каких именно из испытаний будут успехи

Это один из главных мостов между комбинаторикой и вероятностными моделями: коэффициент появляется не как “алгебраическая магия”, а как подсчёт числа сценариев.

Краткая памятка

| Идея | Что означает | Формула | |---|---|---| | Биномиальный коэффициент | выбрать из без порядка | | | Симметрия | выбрать или оставить | | | Правило Паскаля | разбиение по “особому” элементу | | | Бином Ньютона | раскрытие | | | Сумма коэффициентов | число подмножеств | |

Источники для справки

Биномиальный коэффициент (Википедия)

Бином Ньютона (Википедия)

Треугольник Паскаля (Википедия)

Включения-исключения, Дирихле и рекуррентные методы

В прошлых темах мы научились считать варианты через правила сложения и умножения, работать с , , и биномиальными коэффициентами , а также увидели, как комбинаторика “встраивается” в вероятность (например, в схему Бернулли). Но в реальных задачах часто появляется новая трудность: множества вариантов пересекаются, или структуру объектов удобнее считать по частям, строя зависимость от меньших случаев.

В этой статье разберём три мощных инструмента:

принцип включения–исключения (аккуратно считает объединения и исправляет “двойной счёт”),

принцип Дирихле (гарантирует существование совпадений при “слишком большом” числе объектов),

рекуррентные методы (считаем сложные структуры через более простые).

Принцип включения–исключения

Зачем он нужен

Правило сложения работает, когда варианты взаимоисключающие. Но если условия могут выполняться одновременно, прямое сложение даёт “двойной” (или тройной и т.д.) счёт.

В первой теме мы уже видели формулу для двух множеств:

Здесь:

и — множества вариантов,

— количество элементов в ,

— элементы, которые в или в ,

— элементы, которые одновременно в и в .

Минус нужен, потому что элементы из пересечения при сложении были посчитаны дважды.

Для трёх множеств

Если есть три множества , , , то формула становится:

Что означает каждая часть:

— складываем мощности по отдельности,

— вычитаем то, что было посчитано дважды,

— добавляем обратно то, что вычли лишний раз: элементы, попавшие во все три множества, при вычитании парных пересечений “перестарались” и убрали их слишком сильно.

!Диаграмма Венна для понимания знаков в формуле для трёх множеств

Пример: числа, кратные 2 или 3 или 5

Сколько чисел от 1 до 100 делятся на 2 или на 3 или на 5?

Определим множества:

— кратные 2,

— кратные 3,

— кратные 5.

Считаем мощности:

,

,

.

Пересечения:

— кратные 6: ,

— кратные 10: ,

— кратные 15: .

Тройное пересечение — кратные : .

Подставляем:

Здесь важно понимать роль каждого слагаемого:

первые три числа (50, 33, 20) — “наивное сложение”,

три вычитания (16, 10, 6) — исправляют двойной счёт,

последнее добавление (3) — исправляет “перевычитание” элементов, которые лежат во всех трёх множествах.

Общая идея для множеств

Если множеств много, принцип остаётся тем же: мы складываем мощности одиночных множеств, вычитаем мощности всех попарных пересечений, добавляем мощности всех тройных пересечений и так далее, чередуя знаки.

Удобно запомнить так:

пересечения из 1 множества — со знаком плюс,

пересечения из 2 множеств — со знаком минус,

пересечения из 3 множеств — снова плюс,

далее знаки чередуются.

В вероятностях включение–исключение встречается как формула для вероятности объединения событий, например:

Здесь:

— вероятность события,

“пересечение” означает, что произошли оба события,

логика со знаками точно такая же, как при подсчёте количества вариантов.

Принцип Дирихле (принцип ящиков)

Базовая формулировка

Если разложить объектов по ящикам, то хотя бы в одном ящике окажется минимум 2 объекта.

Здесь:

“объекты” — то, что мы распределяем (люди, числа, шарики),

“ящики” — категории (месяцы рождения, остатки при делении, комнаты).

Это не формула, а логическая гарантия: иногда задача просит не “сколько”, а “докажите, что обязательно существует”.

!Иллюстрация базовой идеи принципа Дирихле

Усиленная формулировка

Если разложить объектов по ящикам, то существует ящик, в котором лежит как минимум

элементов.

Пояснение записи:

— число объектов,

— число ящиков,

— среднее число объектов на ящик,

— округление вверх (минимальное целое число, не меньшее ).

Почему это верно по смыслу: если бы в каждом ящике было строго меньше , то суммарно объектов не хватило бы до .

Типовые применения

Совпадения по остаткам: если взять достаточно много целых чисел, у двух будет одинаковый остаток при делении на (ящики — остатки ).

Задачи “в группе найдутся двое…”: ящики — категории (месяцы, цвета, районы).

Гарантированная плотность: “в каком-то месте обязательно тесно”.

Важно: принцип Дирихле часто используется вместе с комбинаторным моделированием — сначала нужно придумать, что считать ящиками.

Рекуррентные методы счёта

Что такое рекурсия в комбинаторике

Иногда прямую формулу получить трудно, но можно:

описать, как устроен объект,

разбить все варианты на несколько типов,

выразить число вариантов длины/размера через числа для меньших .

Так появляется рекуррентное соотношение.

Рекурсия почти всегда состоит из двух частей:

рекуррентная формула (как получить из предыдущих),

начальные условия (значения для маленьких , чтобы рекурсия “запустилась”).

Пример: двоичные строки без двух единиц подряд

Пусть — количество двоичных строк длины (из символов 0 и 1), в которых нигде нет подстроки 11.

Разобьём все допустимые строки длины по последнему символу:

если строка оканчивается на 0, то первые символов могут быть любой допустимой строкой длины — таких ,

если строка оканчивается на 1, то предпоследний символ обязан быть 0, а первые символов могут быть любой допустимой строкой длины — таких .

Это даёт рекурсию:

Здесь:

— число допустимых строк длины ,

— вклад строк, оканчивающихся на 0,

— вклад строк, оканчивающихся на 01.

Начальные условия удобно взять такими:

(строки: 0, 1),

(строки: 00, 01, 10).

Дальше можно считать по формуле: , и т.д. Получается последовательность Фибоначчи (сдвинутая), но для задач часто достаточно самой рекурсии и аккуратного вычисления.

Пример: замощение полоски доминошками

Пусть — число способов замостить прямоугольник доминошками .

Посмотрим на самый левый край:

если поставить одну доминошку вертикально, остаётся прямоугольник — это вариантов,

если поставить две доминошки горизонтально (они обязательно идут парой), остаётся прямоугольник — это вариантов.

Получаем:

Начальные условия:

(только вертикальная доминошка),

(две вертикальные или две горизонтальные).

!Схема разбиения случаев для вывода рекурсии

Как “правильно” строить рекурсию

Чтобы рекурсия действительно работала, полезно придерживаться шаблона:

определить величину одним предложением (что именно считаем),

выбрать “точку разреза” (первый элемент, последний элемент, положение особого объекта),

разбить варианты на непересекающиеся типы,

для каждого типа показать взаимно-однозначное соответствие с объектами меньшего размера,

записать сумму вкладов.

Связь с вероятностями

Рекурсии возникают в вероятностных моделях, когда нужно считать количество допустимых траекторий/последовательностей (например, без запрещённых шаблонов) или когда вероятность выражается через “шаг назад” (это уже похоже на динамическое программирование и марковские цепи). Комбинаторная часть — в правильном подсчёте числа сценариев.

Когда какой метод выбирать

| Ситуация | Типичный признак | Метод | |---|---|---| | Считаем “ или или ”, условия пересекаются | при сложении появляется двойной счёт | включение–исключение | | Нужно доказать, что совпадение обязательно есть | объектов больше, чем категорий | Дирихле | | Объект строится по шагам, и видна зависимость от меньших размеров | можно разрезать на случаи и получить зависимость от , и т.д. | рекурсия |

Ссылки для справки

Принцип включения — исключения

Принцип Дирихле

Рекуррентное соотношение

Комбинаторика в теории вероятностей: классические модели

Комбинаторика в вероятностях нужна для одного простого действия: корректно посчитать количество исходов. В прошлых статьях мы научились отличать порядок от непорядка, учитывать повторения, пользоваться биномиальными коэффициентами и принципом включения–исключения. Теперь соберём это в набор классических вероятностных моделей, где вероятность выражается через отношение количеств.

Классическая модель вероятности

Классическая (лапласовская) модель применяется, когда:

множество элементарных исходов конечно;

все элементарные исходы считаются равновозможными.

Если — множество всех исходов, а событие , то

Разбор формулы:

— вероятность события ;

— число исходов, которые приводят к событию ;

— число всех элементарных исходов;

дробь означает, что вероятность — это доля благоприятных исходов.

Ключевая трудность почти всегда в том, чтобы правильно задать и аккуратно посчитать .

!Ω| и |A|, формула P(A)=|A|/|Ω|. Стиль учебной инфографики, белый фон, 2–3 цвета, без лишних деталей | Наглядно показывает идею вероятности как доли исходов

Как выбрать пространство исходов

Один и тот же сюжет можно моделировать по-разному, и это влияет на равновозможность.

Если мы считаем упорядоченные последовательности (например, вытягивания по очереди), то обычно элементарный исход — это последовательность.

Если мы считаем набор без порядка (например, «какие карты оказались в руке»), то элементарный исход — это набор.

Правило: выбирайте такие элементарные исходы, которые действительно равновозможны в вашем эксперименте.

Модель «урна без возвращения» и гипергеометрическая логика

Сюжет: в урне шаров, из них «успешных» (например, красных), и мы достаём шаров без возвращения. Нужно найти вероятность ровно успешных.

Если порядок доставания не важен (часто так и есть), естественно считать исходы как набор из шаров.

Общее число наборов: .

Почему: мы выбираем объектов из без учёта порядка.

Благоприятные наборы: выбрать успешных из и неуспешных из :

Разбор:

— сколько способов выбрать успешных шаров из всех успешных;

— сколько способов выбрать недостающие шаров из неуспешных.

Итого вероятность:

Разбор формулы:

— число успешных шаров среди выбранных ;

числитель — количество благоприятных наборов;

знаменатель — количество всех равновозможных наборов.

Это и есть классический комбинаторный вывод вероятностей для того, что в теории вероятностей называют гипергеометрическим распределением.

Модель «с возвращением» и схема Бернулли

Теперь пусть мы делаем независимых испытаний, где в каждом:

успех случается с вероятностью ;

неуспех — с вероятностью .

Например: подбрасывания монеты, выстрелы по мишени, выбор шара с возвращением (когда состав урны не меняется).

Вероятность ровно успехов:

Что означает каждая часть:

— сколькими способами можно выбрать, в каких именно испытаниях были успехи;

— вероятность конкретного шаблона, где успех случился в этих позициях (перемножаем раз);

— вероятность того, что в остальных испытаниях успеха нет.

Связь с комбинаторикой прямая: биномиальный коэффициент считает количество различных расположений успехов.

!Дерево демонстрирует, откуда берётся множитель C(n,k) в формуле Бернулли

Карты и кости: два типовых пространства исходов

Кубики

Если бросаем два честных кубика, естественное — все упорядоченные пары , где . Тогда:

(правило умножения).

Событие «сумма равна 7» соответствует 6 исходам:

, , , , , .

Значит, .

Здесь важно, что порядок в паре считается: и — разные элементарные исходы.

Карты (покерная рука)

Если из колоды берут 5 карт и порядок не важен, естественное — все 5-карточные наборы:

.

Дальше любое событие считается через подсчёт количества соответствующих 5-карточных наборов. Главная идея та же: выберите модель исходов так, чтобы они были равновозможны.

Вероятность через дополнение

Комбинаторный подсчёт часто упрощается, если вместо события считать дополнение :

Разбор:

— событие « не произошло»;

единица появляется потому, что в классической модели .

Пример-типаж: «хотя бы одно совпадение»

Сюжеты вроде «хотя бы один успех», «хотя бы одна нужная карта», «хотя бы два человека с одинаковым днём рождения» часто проще решаются так:

считать вероятность что совпадений нет;

вычесть из 1.

Именно поэтому в предыдущих темах мы подчёркивали технику дополнения.

Включение–исключение в вероятностных событиях

Если событие — это «произошло или », а они могут пересекаться, то:

Разбор:

— произошло хотя бы одно;

— произошло оба;

вычитание нужно, потому что при сложении пересечение учтено дважды.

Это ровно та же логика, что и для подсчёта мощностей множеств в комбинаторике, только вместо стоит .

Модель распределения по ячейкам: мультиномиальная идея

Сюжет: делаем независимых испытаний, и в каждом возможен один из исходов с вероятностями , где . Пусть за испытаний исход случился раз, причём .

Сколько существует последовательностей, в которых ровно раз встретился исход 1, раз — исход 2, и так далее?

Ответ (комбинаторика перестановок с повторяющимися элементами):

Разбор:

— сколько было бы последовательностей, если бы все позиций были «разными метками»;

деление на убирает лишний счёт из-за того, что перестановки одинаковых исходов между собой не меняют последовательность.

Тогда вероятность получить именно такие количества равна:

Что означает каждый множитель:

дробь — число последовательностей с нужными счётчиками;

— вероятность того, что исход реализовался раз (перемножение независимых шагов).

Эта конструкция лежит в основе многих задач «распределить результаты по категориям».

Типовые ошибки и как их избегать

Перепутали порядок: выбрали там, где исход — последовательность (нужно ), или наоборот.

Смешали равновозможность: разные исходы имеют разные вероятности, но их считают как одинаковые.

Не заметили зависимость: в «без возвращения» испытания зависимы, и формула Бернулли неприменима.

Не воспользовались дополнением: прямой подсчёт сложен, хотя событие «не произошло ни разу» считается в одну строку.

Куда это ведёт дальше

Классические модели дают общий язык для вероятностных задач:

выбор правильного ;

подсчёт через , , включение–исключение;

переход от подсчёта к вероятности как к доле.

Дальше эти идеи естественно переходят к более продвинутым темам: оценкам вероятностей, асимптотике, случайным процессам и комбинаторным вероятностным моделям, где считать приходится уже не только формулами, но и рекурсиями.

Ссылки для справки

Классическое определение вероятности