EssayAI
Блог
Блог
Естественные науки

Метод шаров и перегородок: формулы и примеры

8 ноября 2026Время чтения: 8 минут
#метод шаров и перегородок#комбинаторика#сочетания#целочисленные решения#распределения
Метод шаров и перегородок: формулы и примеры

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

Как работает представление шарами

Пусть есть пять одинаковых шаров и три коробки: первая, вторая и третья. Выложим шары в ряд и поставим две перегородки. Шары до первой перегородки попадут в первую коробку, между перегородками - во вторую, а после второй - в третью. Так запись ∙∙∣∙∣∙∙\bullet\bullet|\bullet|\bullet\bullet обозначает распределение (2,1,2)(2,1,2).

Перегородка меняется местами с соседним шаром: один шар переходит между соседними ячейками, после чего исходное распределение восстанавливается.

Если перегородка стоит у начала или конца ряда, крайняя коробка пуста. Соседние перегородки означают пустую среднюю коробку: например, ∙∙∣∣∙∙∙\bullet\bullet||\bullet\bullet\bullet соответствует (2,0,3)(2,0,3). Пустая коробка здесь не ошибка, пока условие её не запрещает.

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

Формула для неотрицательных количеств

Пусть nn одинаковых шаров распределяют по kk различимым ячейкам, причём n≥0n\geq 0, k≥1k\geq 1, и оба числа целые. Для kk ячеек нужно k−1k-1 перегородок. Всего в ряду n+k−1n+k-1 позиций; достаточно выбрать из них места перегородок. Получаем число распределений:

N=(n+k−1k−1)=(n+k−1n).N=\binom{n+k-1}{k-1}=\binom{n+k-1}{n}.

Обе записи равны: можно выбирать позиции перегородок или оставшиеся позиции шаров. Это обычное сочетание: порядок выбранных позиций сам по себе не важен. Но порядок ячеек важен: (2,1,2)(2,1,2) и (1,2,2)(1,2,2) - разные результаты, потому что коробки различимы.

Для пяти шаров и трёх коробок в последовательности семь позиций, из которых две занимают перегородки. Значит, N=(72)=7⋅6/2=21N=\binom72=7\cdot6/2=21. При одной коробке перегородок нет и ответ всегда равен единице. При нуле шаров и разрешённых пустых коробках тоже ровно одно распределение: все количества равны нулю.

Пять шаров и две перегородки: 21 распределение с пустыми ячейками и 6 без пустых
Пять шаров и две перегородки: 21 распределение с пустыми ячейками и 6 без пустых

Если каждая ячейка должна быть непустой

Теперь требуем, чтобы в каждой коробке лежал хотя бы один шар. Если n<kn<k, это невозможно: ответ равен нулю. При n≥kn\geq k сначала положим по одному шару в каждую коробку. Останется n−kn-k одинаковых шаров, которые можно распределять уже без ограничений на пустоту. Формула предыдущего раздела даёт

N+=((n−k)+k−1k−1)=(n−1k−1).N_+=\binom{(n-k)+k-1}{k-1}=\binom{n-1}{k-1}.

В примере после обязательной раздачи остаются два шара. Их распределяют по трём коробкам (42)=6\binom42=6 способами. После возврата обязательных шаров получаются тройки (3,1,1)(3,1,1), (1,3,1)(1,3,1), (1,1,3)(1,1,3), (2,2,1)(2,2,1), (2,1,2)(2,1,2) и (1,2,2)(1,2,2).

Есть и второй взгляд: между пятью шарами имеются четыре внутренних промежутка. Если поставить две перегородки в разные промежутки, каждая коробка получит шар. Выбор двух промежутков из четырёх снова даёт (42)=6\binom42=6. Ставить перегородки на концах или вместе в одном промежутке здесь нельзя: возникла бы пустая коробка.

Уравнения и нижние границы

Число распределений равно числу целочисленных решений уравнения x1+⋯+xk=nx_1+\dots+x_k=n при xi≥0x_i\geq0: переменная xix_i просто обозначает количество шаров в ii-й ячейке. Это позволяет перейти от рисунка к алгебре, не меняя сути задачи.

Если заданы нижние границы xi≥aix_i\geq a_i, где все aia_i целые, сделаем замену yi=xi−aiy_i=x_i-a_i. Тогда yi≥0y_i\geq0, а их сумма равна R=n−∑iaiR=n-\sum_i a_i. При R<0R<0 решений нет; при R≥0R\geq0 их (R+k−1k−1)\binom{R+k-1}{k-1}. Замена обратима: к каждому yiy_i снова прибавляем соответствующее aia_i.

Например, для x+y+z=10x+y+z=10 при x≥2x\geq2, y≥1y\geq1, z≥0z\geq0 сначала резервируем три единицы. Остаётся R=7R=7, поэтому ответ равен (92)=36\binom92=36. Важно вычесть именно сумму обязательных минимумов, а не просто число переменных.

Верхние границы и неравенства

Обычная формула не учитывает вместимость коробок. Допустим, в примере с пятью шарами первая коробка вмещает не более двух. Из 21 распределения исключаем те, где в ней не меньше трёх. После резервирования трёх шаров в первой коробке остаются два свободных шара; запретных распределений (42)=6\binom42=6. Значит, допустимых 21−6=1521-6=15.

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

Для неравенства x1+⋯+xk≤nx_1+\dots+x_k\leq n с неотрицательными целыми переменными можно ввести остаток xk+1=n−∑ixix_{k+1}=n-\sum_i x_i. Он показывает, сколько единиц не использовано. Получается равенство с k+1k+1 переменными и ответ (n+kk)\binom{n+k}{k}. Этот приём работает, когда остаток действительно может быть любым неотрицательным целым числом. Пример такой дополнительной ячейки приведён в решениях MIT.

Когда модель подходит в программировании

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

Но если задания различимы и важно, какое именно попало в какую очередь, модель меняется. Для каждого из nn различимых заданий выбирают одну из kk очередей, получая knk^n назначений при разрешённых пустых очередях. Такой подсчёт опирается на правило произведения. Одинаковые шары в исходной модели не имеют личных меток, и их перестановка внутри коробки нового результата не создаёт.

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

Как выбрать модель перед подсчётом

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

Рассмотрим распределение четырёх одинаковых токенов между двумя процессами. Вектор (0,4)(0,4) означает, что первому процессу не досталось ни одного токена; вектор (4,0)(4,0) описывает другую ситуацию, так как процессы имеют разные роли. Всего возможны пять векторов: первая координата принимает значения от нуля до четырёх, а вторая определяется остатком. Формула даёт тот же ответ: (51)=5\binom51=5. Если оба процесса должны получить токен, остаются три вектора, и ответ совпадает с (31)=3\binom31=3.

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

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

Частые ошибки

  • Использовать kk перегородок для kk коробок. В ряд нужны только k−1k-1 внутренних разделителей.
  • Запрещать соседние перегородки без основания. Они нужны для представления пустых внутренних коробок.
  • Применять формулу непустых ячеек при n<kn<k. В этом случае ответ ноль; формулу с отрицательными верхними индексами использовать не нужно.
  • Не проверить различимость предметов и ячеек. Различимые предметы или неразличимые коробки задают другую задачу.
  • Игнорировать предел вместимости. Верхние границы требуют дополнительного подсчёта запрещённых вариантов.

FAQ

Почему перегородок на одну меньше, чем ячеек?

Два края ряда уже ограничивают крайние ячейки. Каждая внутренняя перегородка добавляет ещё одну ячейку: одна разделяет ряд на две части, две - на три.

Можно ли считать сочетания с повторениями?

Да. Выбор nn предметов из kk видов с повторениями и без учёта порядка задаётся количествами предметов каждого вида. Это те же неотрицательные решения с суммой nn, поэтому их число равно (n+k−1k−1)\binom{n+k-1}{k-1}.

Все ли распределения одинаково вероятны?

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

Коротко

Шары кодируют одинаковые предметы, а k−1k-1 перегородок отделяют kk различимых ячеек. При разрешённых нулях ответ равен (n+k−1k−1)\binom{n+k-1}{k-1}; при положительных количествах и n≥kn\geq k - (n−1k−1)\binom{n-1}{k-1}. Перед вычислением проверьте различимость, допустимость пустых ячеек и все границы: именно они определяют модель.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Тождество Вандермонда: формула и доказательство

Тождество Вандермонда: формула и доказательство

Тождество Вандермонда связывает сумму произведений биномиальных коэффициентов с одним сочетанием. Разбираем доказательства, пример и применение в вероятности.

8 ноября 20269 минут
Вероятность через сочетания: формула и разбор

Вероятность через сочетания: формула и разбор

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

20 июня 20267 минут
Числа Белла: разбиения множества и формула

Числа Белла: разбиения множества и формула

Числа Белла считают разбиения множества на непустые группы. Разбираем подробные примеры, рекуррентную формулу, связь с числами Стирлинга и алгоритм вычисления.

8 ноября 20269 минут
Диаграммы Юнга: разбиения, таблицы и формула крюков

Диаграммы Юнга: разбиения, таблицы и формула крюков

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

8 ноября 20268 минут
Комбинаторика: размещения и формулы подсчёта

Комбинаторика: размещения и формулы подсчёта

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

8 ноября 20268 минут
Мультимножество: кратности, операции и примеры

Мультимножество: кратности, операции и примеры

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

8 ноября 20268 минут