Число сочетаний (2 часть). Напишем С(0, 0). Ниже напишем С(1, 0) и С(1, 1). Ещё ниже напишем С(2, 0), С(2, 1), С(2, 2) и так далее (как на рисунке). Заметим, что каждое число в этом "треугольнике" является суммой двух соседних чисел в предыдущей строке (кроме крайних единичек). И вправду, это подтверждает формула С(n + 1, k + 1) = С(n, k + 1) + C(n, k). Такой треугольник называют треугольником Паскаля. С помощью треугольника Паскаля можно решать некоторые комбинаторные задачи. Одна из них: Допустим паук стоит на нулевой строке треугольника Паскаля (на числе 1). Паук может двигаться либо вниз влево, либо вниз вправо. Сколько способов у него добраться в какую-то какую-то клетку. В этой задаче можно воспользоваться свойством треугольника Паскаля: число в треугольнике показывает, сколько способов этому пауку добраться до этого числа. Доказать это можно так: количество способов добраться пауку в какое-то число равно сумме количества способов добраться до числа вверху влево и до числа вверху вправо.