🔺 Pascal's Triangle mod p

Zgodnie z twierdzeniem Lucasa, C(n,k) mod 2 wynosi 1 dokładnie wtedy, gdy każda cyfra binarna k jest mniejsza lub równa odpowiadającej cyfrze binarnej n (równoważnie, k AND n = k). Kolorowanie komórek, dla których to zachodzi, i pozostawienie reszty pustych daje, wiersz po wierszu, dokładnie ten sam rekurencyjny wzór trójkątnych dziur co klasyczna konstrukcja trójkąta Sierpińskiego — nie przybliżenie, lecz dokładne dopasowanie na poziomie bitów.

Twierdzenie Lucasa mówi, że dla liczby pierwszej p, C(n,k) mod p można obliczyć, zapisując n i k w podstawie p cyfra po cyfrze i mnożąc współczynniki dwumianowe odpowiadających sobie cyfr mod p: C(n,k) ≡ ∏ C(n_i,k_i) (mod p). Jeśli którakolwiek cyfra k przekracza odpowiadającą cyfrę n, jeden z tych czynników wynosi zero, więc cały iloczyn wynosi zero — dlatego właśnie tam, gdzie się pojawiają, są puste (zerowe) komórki.

Twierdzenie Lucasa stosuje się dla dowolnej liczby pierwszej, ale reguła porównywania cyfr działa w podstawie p, a nie w podstawie 2. Dla p = 3 trójkąt jest podzielony na samopodobny układ kopii w skali 3×3 zamiast 2×2, a możliwych jest więcej klas reszt (0, 1, 2, ...), więc wzór ma bogatsze wewnętrzne kolorowanie i inną symetrię niż ściśle binarny przypadek Sierpińskiego.

Prawdziwa wartość C(256,128) ma około 75 cyfr, znacznie przekraczając to, co mieści się w standardowych liczbach całkowitych 32- lub 64-bitowych, i wymagałaby powolnej arytmetyki dowolnej precyzji, aby ją dokładnie obliczyć. Ponieważ potrzebna jest tylko reszta mod p, każdą sumę pośrednią można zredukować z powrotem do liczby między 0 a p−1 na każdym kroku, utrzymując całą arytmetykę w małych, szybkich liczbach całkowitych bez względu na liczbę obliczanych wierszy.

Poza tym, że jest to wizualnie uderzający fraktal, współczynniki dwumianowe mod p są kluczowe w kombinatoryce na ciałach skończonych, teorii kodowania i automatach komórkowych (trójkąt Pascala mod 2 jest ściśle powiązany z Regułą 90 w klasyfikacji elementarnych automatów komórkowych Wolframa). Ta sama cyfrowa struktura wynikająca z twierdzenia Lucasa pojawia się także w szybkich algorytmach obliczania współczynników dwumianowych modulo liczba pierwsza w programowaniu konkursowym i kryptografii.