Четыре связанные задачи помогают различать выбор позиций, размещение с ограничениями и распределение одинаковых предметов. Во всех случаях ответ нужно записать одним биномиальным коэффициентом.
Обозначение
C(n, k) — число способов выбрать k объектов из n без учёта порядка: C(n, k) = n!/[k!(n − k)!]. Буквы одного вида и яблоки в этих задачах не различаются; люди, напротив, различны.
1. Слова из четырёх А и шести Б
Условие: сколько существует различных последовательностей, содержащих ровно четыре буквы А и шесть букв Б?
Всего десять позиций. Выбираем четыре позиции для А; шесть оставшихся автоматически заполняются Б. Каждому набору позиций соответствует ровно одно слово.
Ответ: C(10, 4) = 210.
Переставлять четыре одинаковые А между уже выбранными местами не нужно: такая перестановка не создаёт нового слова.
2. Буквы А не должны идти подряд
Условие: сохраняются четыре А и шесть Б, но никакие две А не могут соседствовать.
Сначала расположим шесть Б. Между ними и по краям образуется семь промежутков:
_ Б _ Б _ Б _ Б _ Б _ Б _
Для отсутствия соседних А в один промежуток можно поставить не более одной А. Выбираем четыре разных промежутка из семи.
Ответ: C(7, 4) = 35.
3. Четыре одинаковых яблока, не больше одного человеку
Условие: раздать все четыре одинаковых яблока десяти разным людям, не дав никому больше одного.
Нужно выбрать четырёх получателей из десяти. Выбор однозначно определяет раздачу; порядок передачи яблок не считается новым вариантом.
Ответ: C(10, 4) = 210.
4. Четыре одинаковых яблока без ограничения
Условие: раздать все четыре яблока десяти людям; каждый может получить любое неотрицательное число яблок.
Если xᵢ — число яблок у человека i, нужно посчитать неотрицательные целочисленные решения x₁ + … + x₁₀ = 4.
Представим четыре яблока четырьмя звёздочками, а десять получателей отделим девятью перегородками. Перегородки могут стоять рядом: это означает ноль яблок у соответствующего человека. Всего тринадцать символов, из которых выбираем четыре места для звёздочек.
Ответ: C(13, 4) = 715.
Как выбирать метод
В первой и третьей задачах выбирается обычное подмножество позиций или получателей. Во второй ограничение удобнее учитывать через свободные промежутки. В четвёртой допускаются повторные получатели, поэтому нужен подсчёт неотрицательных решений, а не C(10, 4).
Все четыре биномиальных коэффициента приведены в источнике. Объяснения, схемы и численные значения добавлены редакцией.
Связанные материалы
Элементы дискретной математики · Математика.
Борис Демешев и участники probability_pro · задача 5.2 · CC BY 4.0. Адаптировано; ответы дополнены объяснениями.