Pascal's Triangle as Fractals

Współczynniki dwumianowe, po kolei w jednym rzędzie

Trójkąt Pascala buduje rząd n z rzędu n−1 zgodnie z zasadą: każda wartość jest sumą dwóch wartości znajdujących się powyżej niej o jedną komórkę, a brzegi są uzupełnione jedynkami. W rządzie n, na pozycji k, znajduje się współczynnik dwumianowy C(n, k) – liczba sposobów wyboru k elementów z n, oraz współczynnik xᵏ w rozwinięciu (1 + x)ⁿ. Nazwa pochodzi od traktatu Blaise Pascala z 1654 roku, choć sam trójkąt był znany na wieki wcześniej w Indiach, Persji i Chinach (gdzie nazywany jest trójkątem Yang Hui’ego). Kolorowanie każdej komórki według jej wartości modulo małego przedziału liczbowego p przekształca ten zwykły zestaw kombinatoryczny w wyświetlanie samopodobnej struktury fraktalnej.

row[0] = [1]
row[n][k] = row[n-1][k-1] + row[n-1][k]     (with row[n][0] = row[n][n] = 1)

// reduced mod p, this is all that's needed:
cellModP = (row[n-1][k-1] + row[n-1][k]) % p

demo na żywo · powiązana symulacja● LIVE

Moduł 2: Trójkąt Sierpińskiego pojawia się bez wysiłku

Zaznacz każdą nieparzystą liczbę czarną, a każdą parzystą białą, a trójkąt Pascala modulo 2 staje się dokładnie trójkątem Sierpińskiego – nie przybliżeniowo, a z niezwykłą precyzją. Resemblance staje się ostra w miarę obliczania kolejnych wierszy, a nie jest to przypadek kilku kilkudziesięciu wierszy. Nie jest to błąd wizualizacji; jest to twierdzenie. Twierdzenie Lucasa (1878) mówi, że C(n, k) mod p (dla liczby pierwszej p) można obliczyć cyfrę po cyfrze w podstawie p: zapisz n i k w podstawie p jako n = nₘ...n₁n₀ i k = kₘ...k₁k₀, wtedy C(n, k) mod p = iloczyn C(nᵢ, kᵢ) mod p dla każdej pozycji cyfry, a cały iloczyn jest równy zeru (mod p) natychmiast, gdy każdy parzysta cyfra nᵢ > kᵢ. Dla p = 2, oznacza to, że C(n, k) jest liczbą nieparzystą dokładnie wtedy, gdy wszystkie bity binarne k są ≤ odpowiadającym im bitom binarnym n – precyzyjnie warunek rekurencyjny "czy bit jest podzbiorem bitu" generujący wzorzec rekurencyjnego usuwania charakterystyczny dla gąsienicy Sierpińskiego.

Inne liczby pierwsze: fraktale z rozgałęzianiem o współczynniku p

Teorety Lucas tenormalizuje się czysto dla dowolnej liczby pierwszej *p*, a otrzymany wzor mod-*p* jest ponownie samopodobny, ale teraz zbudowany z *p*( *p* + 1) / 2 mniejszych, podobnych kopii ułożonych w trójkątnym superstrukturze, zamiast przypadku 3 kopii (trójkąt Sierpińskiego dla mod-2),.

Wzór dla mod-3 pokazuje wzor na trójkątne komórki z sześciokrotną strukturą wewnętrzną; dla mod-5 i mod-7 wzory stają się stopniowo bardziej wyrafinowane i złożone. Każdy z nich ma ściśle obliczalną wymiar fraktala: dla liczby pierwszej *p* wynosi log( *p*( *p* + 1) / 2) / log(*p*) , co równa się log 3 / log 2 ≈ 1,585 dokładnie, gdy *p* = 2 (zwykły wymiar trójkąta Sierpińskiego) i powoli rośnie do 2 w miarę wzrostu *p*, ponieważ większa liczba pierwsza pozwala na to, aby więcej kombinacji cyfr (*n* mod *p*, *k* mod *p*) było niezerowych.

Dlaczego to w ogóle łączy trójkąt Pascala z teorią liczb

Głębokie powody, dla których obiekt czysto kombinatoryczny (liczący podzbiory) redukuje się do reguły czysto opartych na cyfrach (twierdzenie Lucasa), to twierdzenie Kummera: wykładnik liczby pierwszej p dzielący C(n, k) jest równy liczbie przeniesień, gdy dodaje się k i (n − k) w bazie p. Kiedy nie występuje żadnych przeniesień — co dokładnie odpowiada warunkowi "każda cyfra k mieści się w odpowiedniej cyfrze n" — współczynnik dwumianowy nie jest podzielny przez p, więc przetrwa modulo p jako niemożliwy do pominięcia resztę; gdzie występuje przeniesienie, współczynnik jest podzielny przez p i zanika modulo p, tworząc dziury samopodobne, które sprawiają, że wzór fraktalny się pojawia.

Od trójkąta do sztuczki obliczeniowej

Twierdzenie Lucasa nie jest jedynie ozdobą – to praktyczny algorytm. Bezpośrednie obliczanie C(n, k) mod p dla ogromnych n i k (miliony lub więcej) poprzez budowanie pełnego trójkąta jest niewykonalne, ale rozkład n i k na cyfry o podstawie-p i mnożenie ze sobą maksymalnie log_p(n) małych współczynników dwumianowych (każdy wyszukiwany z niewielkiej wstępnie obliczonej tabeli) oblicza odpowiedź w czasie logarytmicznym względem n. Jest to standardowa technika w programowaniu konkurencyjnym i teorii liczb komputerowej, gdy potrzebne jest obliczenie współczynnika dwumianowego modulo małego liczby pierwszej dla bardzo dużych n.

Często zadawane pytania

Dlaczego trójkąt Pascala modulo 2 wygląda identycznie jak trójkąt Sierpinskiego?

Zgodnie z twierdzeniem Lucasa, C(n,k) jest nieparzyste tylko wtedy, gdy każda cyfra binarna k jest mniejsza lub równa odpowiadającej jej cyfrze binarnej n. Ta warunek bitowy podzbioru jest dokładnie tym samym regułą rekurencyjną, która generuje samopodobny wzór wypełnionych i pustych komórek trójkąta Sierpinskiego, więc obie konstrukcje pokrywają się wprost, a nie przybliżeniu.

Czy wzorzec fraktalny występuje dla każdego liczby pierwszego, czy tylko dla 2?

Każda liczba pierwsza p generuje samopodobny wzór fraktalny, gdy trójkąt Pascala jest kolorowany według reszty z dzielenia przez p, zgodnie z tym samym twierdzeniem Lucasa dotyczącym cyfr-po-cyfrach rozszerzonym do podstawy p. Wymiar fraktala rośnie powoli wraz z p, od log(3)/log(2) dla p=2 w kierunku 2, gdy p rośnie, ponieważ większe liczby pierwsze pozwalają na więcej niezerowych kombinacji cyfr.

Czym jest twierdzenie Kummera i jak ono się odnosi do twierdzenia Lucasa?

Twierdzenie Kummera mówi, że wykładnik liczby pierwszej p dzielącej C(n,k) równy jest liczbie przeniesień, które występują podczas dodawania k i n-k w podstawie p. Brak przeniesień oznacza, że współczynnik nie jest podzielny przez p w ogóle (twierdzenie Lucasa o podzbiorze jest spełnione); każde przeniesienie powoduje jego zanik modulo p — przeniesienia są dokładnie tymi, które wycinają samopodobne otwory w fraknie.

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Pascal's Triangle mod p i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.

▶ Otwórz symulację Pascal's Triangle mod p

Pascal's Triangle: A Fractal Mirror