Сочетание как путь

Треугольник Паскаля обычно воспринимают как таблицу чисел:
1
1 1
1 2 1
1 3 3 1
…
Но его можно читать как карту.
Начнём в верхней вершине. На каждом шаге разрешено двигаться вниз влево или вниз вправо.
Если верхнюю строку считать нулевой, после n шагов окажемся в n-й строке. Чтобы попасть в позицию Cₙᵏ, нужно ровно k раз пойти вправо.
А выбрать, на каких именно k шагах из n мы повернём вправо, — это и значит выбрать k элементов из n.
Поэтому число путей к Cₙᵏ равно Cₙᵏ.
Например, сочетанию (2; 5) из пяти элементов соответствует путь, в котором вправо мы идём на втором и пятом шагах:
влево, вправо, влево, влево, вправо.
Всего таких путей C₅² = 10, ровно столько же, сколько существует способов выбрать два элемента из пяти.
Так сочетанию (2; 5) соответствует путь по треугольнику Паскаля: на втором и пятом шагах идём вправо, на остальных — влево.
Из этой картины сразу видна и главная формула треугольника Паскаля.
В любую вершину Cₙᵏ можно попасть последним шагом только двумя способами:
из Cₙ₋₁ᵏ — если последний шаг был влево,
или из Cₙ₋₁ᵏ⁻¹ — если он был вправо.
Поэтому Cₙᵏ = Cₙ₋₁ᵏ + Cₙ₋₁ᵏ⁻¹.
Есть ещё одна связь.
Когда мы нумеровали сочетания в лексикографическом порядке, приходилось пропускать целые блоки сочетаний. Размер каждого такого блока был биномиальным коэффициентом.
На языке путей это становится наглядно: выбирая одну ветвь, мы пропускаем все допустимые продолжения другой. Число таких продолжений — биномиальный коэффициент.
Поэтому те же числа, из которых состоит треугольник Паскаля, естественно возникают и при нумерации сочетаний.
А если начать использовать эти размеры уже не только для подсчёта, но и как веса разрядов, получится новая система счисления — из биномиальных коэффициентов.