Сочетания, целые решения и пути на решётке
Занятие 29 сентября 2026 года. Сочетания, целые решения уравнений и пути на решётке.
Число сочетаний уже встречалось в семинаре о биноме Ньютона. Теперь разберём его подробнее: почему в формуле есть деление на факториал, как меняется подсчёт при повторениях и почему ту же формулу можно использовать для уравнений и путей.
Главный вопрос перед вычислением: что именно считается разными вариантами? Для сочетаний порядок не важен. Для решений уравнения важны значения конкретных переменных. Для пути важна последовательность шагов. Будем каждый раз учитывать именно это.
Сочетания без повторений: выбираем элементы, порядок не учитываем
Пусть есть четыре разных элемента . Выбрать два можно шестью способами:
Записи и означают один и тот же выбор. А здесь не допускается: каждый элемент можно взять только один раз.
Сочетание без повторений из элементов по — это выбор различных элементов из множества
без учёта порядка. Иначе говоря, это подмножество , содержащее ровно элементов. Все элементы исходного множества различны, и — целые числа, .
Число таких выборов обозначают . Это то же обозначение, что в предыдущих материалах.
Формула и доказательство: зачем делить на
Сначала посчитаем выборы, в которых порядок учитывается. Первый элемент можно выбрать способами. Второй — способами, потому что первый уже взят. Для третьего остаётся варианта, и так далее. Получаем
Здесь , а .
В этом подсчёте один и тот же набор из элементов встретился раз: столько существует перестановок его элементов. Например, набор дал бы шесть записей:
Чтобы каждый набор остался посчитан ровно один раз, делим на :
Следовательно,
Деление на убирает повторный подсчёт разных порядков одного выбора. Например,
Для крайних случаев смысл особенно прост:
Не выбрать ничего можно одним способом — получить пустое множество. Взять все элементы тоже можно одним способом. Поэтому число пустых выборов равно одному, а не нулю. При формула также даёт .
Если , выбор без повторений невозможен и его число равно . Факториальную формулу с отрицательным в этом случае не применяют.
Три следствия из формулы сочетаний
1. Симметрия: выбрать элементы или указать оставшиеся
Выбрать элементов из — то же самое, что указать элементов, которые останутся. У каждого выбора есть единственное дополнение, а дополнение однозначно восстанавливает выбор. Поэтому
Например, выбрать два элемента из пяти можно столькими же способами, сколькими можно выбрать три оставшихся:
Это видно и в формуле: множители и в знаменателе просто меняются местами.
2. Сумма всех сочетаний: сколько у множества подмножеств
У множества из элементов есть подмножеств. Почему? Для каждого элемента независимо выбираем одно из двух действий: включить его или не включить. Всего получается вариантов.
Теперь посчитаем те же подмножества по размеру. Пустых — , одноэлементных — , двухэлементных — , и так далее до всего множества. Разные размеры не пересекаются и вместе дают все подмножества:
Знак суммы означает сложение при всех . Пустое подмножество и само множество здесь обязательно учитываются.
3. Правило Паскаля
Для и выполняется
Докажем это равенство двумя способами. Один проверяет формулы, другой объясняет, почему складываются именно эти два числа.
Первое доказательство — через факториалы. Приведём две дроби к общему знаменателю:
Множитель в первой дроби появился из равенства . Множитель во второй — из .
Второе доказательство — через разбиение выборов. Выделим один элемент . Все сочетания из элементов по относятся ровно к одному из двух случаев:
- не выбран. Все элементов выбираем из остальных : получаем вариантов.
- выбран. Одно место уже занято, поэтому из остальных элементов выбираем ещё : получаем вариантов.
Эти случаи не пересекаются и охватывают все выборы. Складывая их числа, получаем правило Паскаля.
На краях, при и , используются уже разобранные значения . В доказательстве через факториалы мы работали с внутренними значениями , чтобы ни в одной дроби не появился факториал отрицательного числа.
Треугольник Паскаля: те же сочетания по строкам
В строке с номером стоят числа
Нумерация начинается с нулевой строки. В строке находится число; крайние числа равны , каждое внутреннее — сумме двух соседних чисел предыдущей строки.
| Номер строки | Числа от до | Сумма строки |
|---|---|---|
Например, число в пятой строке — это . Оно получается из четвёртой строки по правилу Паскаля:
Симметрия строк — это равенство . А сумма каждой строки — уже доказанное равенство . Так треугольник собирает все три следствия в одной картине.
Сочетания с повторениями: считаем, сколько раз взят каждый вид
Теперь повторять элементы разрешено, но порядок по-прежнему не важен. Например, из трёх видов можно выбрать
Тот же выбор в сгруппированном виде — : две буквы , три буквы и две буквы . Это один выбор, записанный в разных порядках.
Сочетание с повторениями из видов по определяется числами
где показывает, сколько раз взят вид . Все целые. Число видов , число выбранных элементов ; для каждого вида повторения не ограничены.
Обозначим число таких сочетаний через . Докажем
Доказательство преподавателя: единицы и разделители
Зафиксируем порядок видов: сначала , затем , и так далее до . Каждое появление элемента запишем единицей, а между видами поставим разделитель :
В примере с двумя , тремя и двумя получается код
В каждом коде ровно единиц и разделителей. Поэтому общая длина кода равна .
Код однозначно задаёт выбор: считаем единицы до первого разделителя, затем между первым и вторым, и так далее. В обратную сторону тоже всё однозначно: по количествам строится единственный код. Следовательно, число выборов равно числу кодов.
Чтобы построить код, достаточно выбрать места для разделителей среди мест. Остальные места займут единицы:
В нашем примере , , поэтому число всех возможных выборов равно
Пустые блоки разрешены. Соседние разделители означают, что соответствующий вид не взяли; разделитель в начале или в конце означает пустой первый или последний блок. Например,
кодирует количества для трёх видов. Запрещать такие коды нельзя: этим мы незаметно потребовали бы взять каждый вид хотя бы один раз.
При есть только пустой выбор: код состоит из разделителей. При разделителей нет, и единственный вид берётся раз. Формула в обоих случаях даёт .
Целые решения уравнения: тот же код решает три задачи
Во всех трёх задачах — целое число, а — заданная целая сумма. Переменные различаются по своим номерам: например, и — разные решения. Поэтому места блоков в коде должны оставаться закреплены за конкретными переменными.
Задача 1. Неотрицательные целые решения
Найти число решений
где — целое число.
Можно представить одинаковых предметов и пронумерованных коробок. В первую кладём предметов, во вторую — , и так далее. Коробки могут быть пустыми.
Для решения записываем единиц в -м блоке и разделяем блоки разделителями. Получается код из единиц и разделителей, общей длины . Поэтому
Например, для решение кодируется как , а число всех решений равно
Если , единственное решение — ; формула даёт .
Задача 2. Положительные целые решения
Теперь требуется
Сначала выделим по одному предмету каждой коробке. На это нужно предметов, значит, при решений нет.
Если , положим
Тогда исходное уравнение равносильно
Это задача о неотрицательных решениях. В её коде единиц и разделителей, всего символов. Получаем
Например, уравнение при имеет три решения:
Формула даёт . При возможно только — снова один вариант.
Задача 3. У каждой переменной своя нижняя граница
Найти число целых решений
где — заданные неотрицательные целые числа. Обозначим их сумму
Сначала в -ю коробку кладём обязательные предметов. После этого нужно распределить ещё предметов без ограничений снизу, кроме неотрицательности.
В формулах тот же переход выглядит так:
Каждому исходному решению соответствует единственный набор , и обратно: . Поэтому число решений сохраняется.
При получаем
Если , даже обязательные количества не помещаются в общую сумму: решений . Если , остаётся единственное решение при всех .
Например,
Здесь , после вычитания нижних границ остаётся . Значит, число решений равно
Все три задачи решаются одной идеей: вычесть обязательные количества, затем посчитать неотрицательные остатки. Во втором случае обязательное количество равно для каждой переменной.
Пути на целочисленной решётке
Целочисленная решётка — точки плоскости с целыми координатами, то есть . Рассмотрим её часть внутри прямоугольника с противоположными вершинами и , где — неотрицательные целые числа.
Узлы решётки — точки с целыми координатами. Ребро соединяет два соседних узла по горизонтали или вертикали. Его длина равна . Диагональный отрезок ребром не является: он изменяет сразу две координаты.
Длина пути здесь — число пройденных рёбер. Разберём две разные задачи: путь до заданной вершины и путь заданной длины с произвольным концом.
Кратчайшие пути от до
Чтобы попасть в , нужно увеличить первую координату на , вторую — на . Поэтому достаточно сделать шагов вправо и шагов вверх; такой путь имеет длину .
Почему короче нельзя? Обозначим числа шагов вправо, влево, вверх и вниз через . Для конечной точки выполняются
Отсюда длина пути равна
Равенство получается ровно при . Значит, кратчайший путь состоит только из шагов вправо и вверх. Такие пути называют монотонными. Они не выходят за пределы прямоугольника.
Закодируем шаг вправо цифрой , а шаг вверх — цифрой . Каждый кратчайший путь превращается в слово длины , содержащее ровно нулей и единиц. И наоборот, любое такое слово задаёт ровно один кратчайший путь до .
Остаётся выбрать места для шагов вверх среди шагов:
Для точки пример кода —
В нём семь нулей и шесть единиц, всего шагов. Число всех кратчайших путей до этой точки равно
Если или , кратчайший путь единственный: все шаги идут в одном направлении. При это пустой путь длины .
Пути длины от начала координат внутри квадрата
Теперь конечная вершина заранее не задана. Нужно посчитать пути из шагов вправо или вверх, начинающиеся в и лежащие внутри квадрата с вершинами и .
На каждом из шагов есть два варианта: вправо или вверх. Ограничение квадрата ничего не исключает: после шагов обе координаты неотрицательны и не больше , а значит, не больше .
Каждая двоичная запись длины задаёт ровно один допустимый путь. Поэтому
Например, при есть четыре пути:
Они заканчиваются соответственно в , , и . Два пути могут прийти в один узел, но остаться разными: порядок шагов у них различается.
После шагов конец любого такого пути лежит на линии . Если шагов вверх ровно , конец равен , а число путей до него — . Складывая по всем возможным концам, получаем знакомое равенство
Условие о шагах вправо и вверх существенно. Число относится именно к этим монотонным путям; для путей с разрешёнными шагами влево или вниз это уже другая задача.
Что объединяет все подсчёты
Во всех задачах мы сначала строили однозначное соответствие:
- Сочетание без повторений — набор выбранных элементов; разные порядки одного набора не создают новых сочетаний.
- Сочетание с повторениями — количества элементов каждого вида; их кодируют единицы и разделители, включая пустые блоки.
- Целое решение — количества в пронумерованных коробках; нижние границы вычитаются до подсчёта остатков.
- Монотонный путь — последовательность шагов; при заданном конце фиксированы количества нулей и единиц, при заданной длине свободен каждый шаг.
Именно это соответствие объясняет формулу. Сначала убедимся, что каждый объект даёт один код, а каждый допустимый код — один объект. После этого остаётся посчитать места для выбранных элементов, разделителей или шагов.
