Алгебра · объяснение и практика

Почему соседние числа треугольника Паскаля складываются

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

Неизвестное x показывает найденное значение — пять.

В теме Последовательности и прогрессии · Учебная карта

Главная мысль

Внутреннее число треугольника Паскаля равно сумме двух соседних над ним: C(n,k) = C(n−1,k−1)+C(n−1,k). Доказательство разбивает все наборы по наличию одного заранее выделенного элемента.

Один элемент делит все случаи на две группы

Нужно выбрать k участников из n разных людей. Выделим одного человека и разделим все допустимые группы на содержащие его и не содержащие. В группу с ним остаётся добрать k−1 участника из n−1, что даёт C(n−1,k−1). В группу без него выбирают все k участников из оставшихся, что даёт C(n−1,k).

Эти случаи не пересекаются и вместе покрывают все группы. Поэтому их количества можно сложить. Здесь правило треугольника становится следствием полного разбиения, а не наблюдением нескольких первых строк. Важно, что выделенный участник один и тот же для обоих случаев; иначе получившиеся классы могли бы пересекаться или пропускать варианты.

Как формула строит новую строку

Если строки нумеровать с нулевой, строка n содержит числа C(n,0), C(n,1), …, C(n,n). На краях стоят единицы: пустое множество и весь набор выбираются единственным способом. Внутренние позиции получаются сложением диагональных соседей предыдущей строки. Поэтому после 1, 4, 6, 4, 1 идёт 1, 5, 10, 10, 5, 1.

Число десять в позиции k = 2 новой строки равно 4+6. Это не сумма соседей слева и справа в той же строке: такая попытка сделала бы правило циклическим и не задала построение. Нумерацию полезно подписывать, особенно если в учебнике начальная строка из одной единицы названа первой, а индекс сочетаний по-прежнему начинается с нуля.

Пример

Сколько способов выбрать троих из семи, если отдельно рассмотреть наличие выделенного участника?

С выделенным участником добираем двоих из шести: C(6,2) = 15. Без него выбираем троих из шести: C(6,3) = 20. Всего 15+20 = 35, что равно C(7,3).

Две независимые проверки целой строки

Сумма строки n равна 2ⁿ: каждый из n элементов либо входит в подмножество, либо нет. Это считает все размеры подмножеств вместе. Симметрия строки объясняется переходом от выбранного набора к дополнению: C(n,k) = C(n,n−k). Обе проверки полезны для обнаружения ошибки в одном внутреннем числе без повторного построения всего треугольника.

Правило работает для целых индексов в обычных комбинаторных границах. На краях можно считать числа вне треугольника нулями, тогда та же сумма даёт единицу. Но такую условность следует оговорить: она не означает, что любой набор отрицательных индексов является обычным количеством выборок. Содержательный смысл выбора сохраняется при n ≥ 0 и 0 ≤ k ≤ n.

От чтения к действию

А теперь — вы

Строка Паскаля равна 1, 5, 10, 10, 5, 1. Какова следующая строка?

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

Почему на краях единицы?

Есть ровно один способ выбрать никого и ровно один способ выбрать весь набор. Эти случаи задают края независимо от внутренних сумм.

Что именно складывается?

Числа из предыдущей строки на диагоналях над нужной позицией. Это соответствует наличию или отсутствию выделенного элемента.

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

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

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