Математика · объяснение и практика
Почему диагональная сумма сочетаний даёт следующее сочетание
Как сумма сочетаний вдоль диагонали треугольника Паскаля превращается в одно сочетание, если классифицировать выбранные наборы по максимальному элементу.

В теме Доказательства и комбинаторные модели · Учебная карта
В маршруте Счёт через устройство объектов · 10 тем
Главная мысль
Для целых n≥r≥0 сумма C(r,r)+C(r+1,r)+…+C(n,r) равна C(n+1,r+1). Разбиение по наибольшему выбранному элементу объясняет каждый член этой суммы.
Следить за двумя индексами
В сумме C(k,r) нижний индекс r остаётся постоянным, а верхний k последовательно увеличивается. Это диагональ треугольника Паскаля, а не сумма всей строки. Начинать нужно с k=r, где сочетание равно единице. При завершении на k=n результат использует сразу два увеличенных индекса: C(n+1,r+1).
Название «хоккейная клюшка» связано с рисунком расположения чисел, но для вычисления надёжнее индексы. Если пропущен начальный член или взят иной диапазон, формула меняется. Сумму от k=s>r можно получить разностью двух полных диагональных сумм. При этом вычитают диапазон до s−1, а не до s.
Наибольший элемент задаёт случай
Рассмотрим все наборы из r+1 элементов множества {1,…,n+1}. Их C(n+1,r+1). Если максимальный элемент равен k+1, остальные r элементов выбираются из {1,…,k}, поэтому таких наборов C(k,r). Возможные максимумы идут от r+1 до n+1, что и даёт все члены диагональной суммы.
Каждый готовый набор имеет ровно один максимум. Поэтому случаи не пересекаются и ни один набор не пропущен. Это важнее внешней формы числового треугольника: тот же довод работает для любого допустимого r. При r=0 каждый одноэлементный набор классифицируется самим своим элементом, и сумма единиц также согласуется с формулой.
Пример
Найдите C(2,2)+C(3,2)+C(4,2)+C(5,2).
Слагаемые 1,3,6,10 дают 20. Это все тройки из {1,…,6}, разбитые по максимуму от 3 до 6, поэтому ответ также равен C(6,3).
Сумма на участке диагонали
Чтобы найти C(5,2)+…+C(9,2), из C(10,3) вычитают C(5,3). Полная сумма от k=2 до 9 содержит также k=2,3,4, а их сумма равна C(5,3). Получается 120−10=110. Такой способ сокращает вычисление длинного участка, но требует явно назвать включённые границы. Другую проверку даёт формула Паскаля: каждое слагаемое записывают как разность двух соседних сочетаний с увеличенным нижним индексом. В сумме промежуточные члены сокращаются, и остаются только граничные. Это объясняет, почему нельзя без изменения ответа сдвинуть начало участка.
Тождество не следует путать с формулой соседних элементов одной строки или с выбором из двух групп. Здесь ключевой классификатор — максимальный элемент одного выбранного набора. Если задача не имеет упорядоченных меток, их можно предварительно назначить различным объектам; подсчёт зависит от количества, а не от конкретных названий этих меток.
От чтения к действию
А теперь — вы
Частые вопросы
Почему сумма начинается с C(r,r)?
Набор из r+1 элементов не может иметь максимум меньше r+1. Именно этому минимальному максимуму соответствует верхний индекс k=r.
Что делать с суммой, начинающейся позже?
Вычесть из полной диагональной суммы пропущенный начальный участок, аккуратно сохранив обе границы.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как выбор из двух групп объясняет тождество Вандермонда
Как выбор фиксированного числа объектов из двух непересекающихся групп объясняет свёртку сочетаний и почему в сумме нужно учитывать все допустимые составы.
Открыть темуКак один набор пар даёт два способа подсчёта
Как доказать равенство двух сумм через один набор пар, выбрать учитываемую связь и проверить, что каждая сторона действительно считает те же объекты.
Открыть тему