Математика · объяснение и практика

Почему диагональная сумма сочетаний даёт следующее сочетание

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

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

В маршруте Счёт через устройство объектов · 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(3,3)+C(4,3)+C(5,3)+C(6,3)?

Частые вопросы

Почему сумма начинается с C(r,r)?

Набор из r+1 элементов не может иметь максимум меньше r+1. Именно этому минимальному максимуму соответствует верхний индекс k=r.

Что делать с суммой, начинающейся позже?

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

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться