Система счисления из сочетаний
Треугольник Паскаля можно использовать не только для подсчёта сочетаний. Из его чисел получается система записи целых чисел.
Зафиксируем число k. Оказывается, любое целое N ≥ 0 можно единственным образом записать в виде
N = Cₐₖᵏ + Cₐₖ₋₁ᵏ⁻¹ + … + Cₐ₁¹,
где aₖ > aₖ₋₁ > … > a₁ ≥ 0.
Будем считать Cₙʳ = 0 при n < r.
Почему такая запись вообще существует?
Её можно строить жадным алгоритмом.
Сначала выбираем наибольший коэффициент Cₘᵏ, не превосходящий N. Пусть это Cₐₖᵏ. Тогда
Cₐₖᵏ ≤ N < Cₐₖ₊₁ᵏ.
Вычтем выбранный коэффициент. Для остатка R получаем
R < Cₐₖ₊₁ᵏ − Cₐₖᵏ.
Но по формуле Паскаля
Cₐₖ₊₁ᵏ − Cₐₖᵏ = Cₐₖᵏ⁻¹.
Значит, R < Cₐₖᵏ⁻¹,
и следующий верхний индекс обязательно можно взять меньше aₖ.
Затем повторяем тот же шаг для коэффициентов с верхним индексом k−1, потом k−2 и так далее.
Так запись всегда строится.
Более того, она единственна: неравенства
Cₐₖᵏ ≤ N < Cₐₖ₊₁ᵏ
однозначно определяют первый индекс aₖ, после чего тот же аргумент применяется к остатку.
Посмотрим на пример:
15 = C₅³ + C₃² + C₂¹ = 10 + 3 + 2.
Действительно, сначала выбираем наибольший коэффициент вида Cₘ³, не превосходящий 15: C₅³ = 10.
Остаётся 5.
Теперь берём наибольший Cₘ² при m < 5: C₃² = 3.
Остаётся 2, то есть C₂¹ = 2.
Если элементы сочетания нумеровать начиная с 1, такой записи естественно сопоставить
(a₁+1; a₂+1; a₃+1).
Поэтому числу 15 соответствует сочетание (3; 4; 6).
Но особенно интересно, что происходит при прибавлении единицы.
Имеем
15 = C₅³ + C₃² + C₂¹.
Тогда
16 = C₅³ + C₃² + C₂¹ + 1.
Сначала
C₂¹ + 1 = 2 + 1 = 3 = C₃¹.
Получается
16 = C₅³ + C₃² + C₃¹.
Теперь срабатывает формула Паскаля:
C₃² + C₃¹ = C₄².
Поэтому
16 = C₅³ + C₄² + C₀¹, где C₀¹ = 0.
Числу 16 соответствует уже сочетание (1; 5; 6).
Это не лексикографический порядок из предыдущего поста, а другой способ нумерации — комбинаторная система счисления.
В обычной позиционной системе числа собираются из степеней основания:
1, b, b², b³, …
Здесь вместо них используются биномиальные коэффициенты, а формула Паскаля выполняет роль правила переноса.
Так треугольник Паскаля превращается из таблицы для подсчёта сочетаний в систему записи целых чисел.
Треугольник Паскаля можно использовать не только для подсчёта сочетаний. Из его чисел получается система записи целых чисел.
Зафиксируем число k. Оказывается, любое целое N ≥ 0 можно единственным образом записать в виде
N = Cₐₖᵏ + Cₐₖ₋₁ᵏ⁻¹ + … + Cₐ₁¹,
где aₖ > aₖ₋₁ > … > a₁ ≥ 0.
Будем считать Cₙʳ = 0 при n < r.
Почему такая запись вообще существует?
Её можно строить жадным алгоритмом.
Сначала выбираем наибольший коэффициент Cₘᵏ, не превосходящий N. Пусть это Cₐₖᵏ. Тогда
Cₐₖᵏ ≤ N < Cₐₖ₊₁ᵏ.
Вычтем выбранный коэффициент. Для остатка R получаем
R < Cₐₖ₊₁ᵏ − Cₐₖᵏ.
Но по формуле Паскаля
Cₐₖ₊₁ᵏ − Cₐₖᵏ = Cₐₖᵏ⁻¹.
Значит, R < Cₐₖᵏ⁻¹,
и следующий верхний индекс обязательно можно взять меньше aₖ.
Затем повторяем тот же шаг для коэффициентов с верхним индексом k−1, потом k−2 и так далее.
Так запись всегда строится.
Более того, она единственна: неравенства
Cₐₖᵏ ≤ N < Cₐₖ₊₁ᵏ
однозначно определяют первый индекс aₖ, после чего тот же аргумент применяется к остатку.
Посмотрим на пример:
15 = C₅³ + C₃² + C₂¹ = 10 + 3 + 2.
Действительно, сначала выбираем наибольший коэффициент вида Cₘ³, не превосходящий 15: C₅³ = 10.
Остаётся 5.
Теперь берём наибольший Cₘ² при m < 5: C₃² = 3.
Остаётся 2, то есть C₂¹ = 2.
Если элементы сочетания нумеровать начиная с 1, такой записи естественно сопоставить
(a₁+1; a₂+1; a₃+1).
Поэтому числу 15 соответствует сочетание (3; 4; 6).
Но особенно интересно, что происходит при прибавлении единицы.
Имеем
15 = C₅³ + C₃² + C₂¹.
Тогда
16 = C₅³ + C₃² + C₂¹ + 1.
Сначала
C₂¹ + 1 = 2 + 1 = 3 = C₃¹.
Получается
16 = C₅³ + C₃² + C₃¹.
Теперь срабатывает формула Паскаля:
C₃² + C₃¹ = C₄².
Поэтому
16 = C₅³ + C₄² + C₀¹, где C₀¹ = 0.
Числу 16 соответствует уже сочетание (1; 5; 6).
Это не лексикографический порядок из предыдущего поста, а другой способ нумерации — комбинаторная система счисления.
В обычной позиционной системе числа собираются из степеней основания:
1, b, b², b³, …
Здесь вместо них используются биномиальные коэффициенты, а формула Паскаля выполняет роль правила переноса.
Так треугольник Паскаля превращается из таблицы для подсчёта сочетаний в систему записи целых чисел.