Трапеція Паскаля: Біноміальні коефіцієнти, Серпінський і Фібоначчі

Одна правило, нескінченний трикутник

Трикутник Паскаля побудовано з одного правила: кожна цифра є сумою двох цифр, що знаходяться по діагоналі зверху, з 1-ками вниз по обох краях. Ряд n, позиція k (обидва починаються з 0) записується як C(n,k), біноміальний коефіцієнт — кількість способів вибрати k елементів із множини з n:

ряд 0: 1 ряд 1: 1 1 ряд 2: 1 2 1 ряд 3: 1 3 3 1 ряд 4: 1 4 6 4 1 ряд 5: 1 5 10 10 5 1 онлайн демо · натисніть на будь-яку клітинку, щоб розкрити C(n,k) та виділити її батьків● LIVE Додавне правило випливає з підрахунку: щоб вибрати k елементів із n, або ви виключаєте останній елемент (вибираєте всі k з решти n−1: C(n−1,k)), або включаєте його (вибираєте решту k−1 з n−1: C(n−1,k−1)). Додавання цих двох підрахунків точно один раз описує кожний дійсний вибір, що є ідентичністю Паскаля: C(n,k) = C(n−1,k−1) + C(n−1,k). Ті самі числа також дорівнюють коефіцієнтам у розкладі (x+y)ⁿ — тому й «біноміальний» коефіцієнт, що пояснює, чому цей трикутник постійно з’являється в алгебрі, не лише в комбінаториці.

row 0:                1
row 1:               1 1
row 2:              1 2 1
row 3:             1 3 3 1
row 4:            1 4 6 4 1
row 5:           1 5 10 10 5 1

Sierpiński трикутник у паральності

Пофарбуйте кожну клітинку за ознакою, чи є C(n,k) непарним або парним, і, дивовижно, з'являється фрактал Sierpińskiego — самоподібний малюнок із вкладеними трикутними дірками. Це не випадкове прикрашання; теорема Куммера пояснює це точно: C(n,k) є непарним лише тоді, коли кожен бінарний розряд k менший або дорівнює відповідному бінарному розряду n (відповідно, коли немає "перенесення" у бінарному додаванні k і n−k). Ця бітова умова самоподібна при подвоєнні n і k, що є рекурсивною структурою, яка генерує фрактал.

Діагоналі приховують Фібоначчі

Обчисліть суми елементів по мінливих діагоналях трикутника (кожен крок рухається вгору на одну рядок і на дві колонки вліво) та отримаєте послідовність Фібоначчі: 1, 1, 2, 3, 5, 8, 13, ... Це пояснюється тим, що рекурентне співвідношення для суми по мінливій діагоналі, відстежуючи структуру додавання в рядках, зводиться до точного F(n) = F(n−1) + F(n−2) — локальне правило додавання трикутника випадково відтворює глобальне Фібоначчі при підсумовуванні вздовж цієї конкретної осі.

diagonal sums (Fibonacci):
  1
  1
  1+1 = 2
  1+2 = 3
  1+3+1 = 5
  1+4+3 = 8

Суми рядів дорівнюють степеням двійки, та інші ідентичності

Якщо сумувати весь рядок, то отримається 2ⁿ — оскільки кожен з n бінарних виборів (включити/виключити) подвоює кількість можливих підмножин, а рядок є точкою переліку підмножини за розміром. Зміна знаків вздовж рядка (+, −, +, −, ...) та сумування дає 0 для кожного рядка після першого, що є прямим наслідком встановлення x = 1, y = −1 у біноміальному розкладі (x+y)ⁿ. Ідентичність хокейної клюшки — підсумовування діагонального пробігу послідовних записів дорівнює єдиному значенню в рядку вниз і на крок вперед — випливає з повторного застосування ідентичності Паскаля, і з'являється у комбінаторних доказах, коли потрібно перетворити суму C(n,k) членів на одне закрите виразне коефіцієнт.

Модульне забарвлення поза рівністю

Рівність (mod 2) дає Sierpiński; забарвлення залишком mod 3, mod 5 або будь-яким простим p виробляє різні, більші самоподібні фрактальні візерунки, кожен з яких регулюється узагальненням теореми Куммера, яке називається теоремою Лукаса: C(n,k) mod p залежить лише від цифр основи-p n та k, порівнюючи цифри одна з одною. Малі p дають більш детальний і щільний фрактальний деталь; трикутник є, у певному сенсі, нескінченною кількістю різних фракталів, що складаються один на одному над тим самим цілочисним сіткою, для кожного вибору модуля, через який ви хочете її бачити.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Pascal's Triangle і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.