Trójkąt Pascala: Współczynniki dwumianowe, Sierpiński i Fibonacci

Jedna reguła, nieskończony trójkąt

Trójkąt Pascalisa jest zbudowany na podstawie jednej reguły: każdy element wynika z sumy dwóch elementów położonych przekątnie wyżej, z 1mi w obu krawędziach. Element n-tego wiersza, k-tego miejsca (obie pozycje liczone są od zera) oznaczany jest jako C(n,k), czyli współczynnik dwumianowy — liczba sposobów wyboru k elementów z zestawu n:

wiersz 0: 1 wiersz 1: 1 1 wiersz 2: 1 2 1 wiersz 3: 1 3 3 1 wiersz 4: 1 4 6 4 1 wiersz 5: 1 5 10 10 5 1 demonstrator interaktywny · kliknij dowolny komórkę, aby odkryć C(n,k) i podświetlić jej rodziców● LIVE Reguła addytywna wynika bezpośrednio z liczenia: wybierając k elementów spośród n, albo wykluczamy ostatni (wybieramy wszystkie k z pozostałych n−1: C(n−1,k)) lub go włączamy (wybieramy pozostałe k−1 z n−1: C(n−1,k−1)). Dodając te dwa wyniki, liczymy każdą prawidłową kombinację dokładnie raz, co jest twierdzeniem Paskala: C(n,k) = C(n−1,k−1) + C(n−1,k). Te same liczby są również współczynnikami przy rozwinięciu (x+y)ⁿ — dlatego mówimy o „dwumianowych” współczynnikach — co wyjaśnia, dlaczego trójkąt pojawia się tak często w algebrze, nie tylko w kombinatoryce.

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 ukryty w parzystości

Koloruj każdy komórkę według tego, czy C(n,k) jest nieparzyste lub parzyste, a zaskakująco pojawia się fraktal trójkąta Sierpińskiego — wzór podobny do siebie z wewnętrznych pustych trójkątów. To nie przypadkowe zjawisko; twierdzenie Kummera wyjaśnia to dokładnie: C(n,k) jest nieparzyste dokładnie wtedy, gdy każdy bitowy cyferka k jest mniejszy lub równy odpowiedniej bitowej cyfrowej n (equivalently, gdy nie ma "przeniesienia" w dodawaniu binarnym k i n−k). Ta warunek bitowy jest podobny do siebie podwójając n i k, co dokładnie odpowiada rekurencyjnej strukturze generującej fraktal.

Dyagonale ukrywają się w ciągu Fibonacciego

Sumując elementy poziomie na dyagonalach głębokich (każde kroku przesuwając się o jeden w górę i dwie w lewo), otrzymujemy ciąg Fibonacciego: 1, 1, 2, 3, 5, 8, 13, ... To działa, ponieważ wzór rekurencyjny dla sumy dyagonalnej głębokiej, po tym jak śledzimy strukturę dodawania w kolumnach, związuje się dokładnie z F(n) = F(n−1) + F(n−2) — przepis dodawania lokalny trójkąta przypadkiem powtarza globalny wzór Fibonacciego, gdy sumujemy po tej konkretnej nachyło.

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

Każda rzędy sumuje się do potęg dwójki i inne identyfikatory

Sumując całą rzęd, otrzymujesz 2ⁿ — ponieważ każda z n dwuczynniczych decyzji (włączyć/oddzielić) podwójnie liczbę podzbiorów możliwych, a rzęd jest dokładnie liczebnością podzbiorów według wielkości. Alternując znaki wzdłuż rzęd (+, −, +, −, ...) i sumując daje 0 dla każdego rzędu po pierwszym, co wynika bezpośrednio z ustawienia x = 1, y = −1 w rozwinięciu binomijnym (x+y)ⁿ. To, co przypomina kij hokejowego — sumując ciąg kolejnych wpisów na przekątnej, otrzymujesz pojedynczy wpis po jednym rzędzie i jednym kroku w dół — wynika z powtarzanej aplikacji tożsamości Pascala. Wykorzystuje się go w dowodach kombinatorycznych, gdy potrzebujesz przekształcić sumę wyrazów C(n,k) w jedno wyrażenie zamkniętego postaci.

Modular koloryzacja poza parzystością

Parzystość (mod 2) daje Sierpińskiego; kolorowanie resztą z dzielenia przez 3, 5 lub dowolną pierwszą liczbę p powoduje wystąpienie innych, większych wzorów samoszybkościowych, które są zarządzane ogólizacją twierdzenia Kummera nazywanego twierdzeniem Lucasa: C(n,k) mod p zależy tylko od cyfr w systemie pozycyjnym o podstawie p liczb n i k, porównywanych cyfry po cyfrze. Małe p daje gęstszy i detaliowy wzór samoszybkościowy; trójkąt jest rzeczywistym sensem wieloma różnymi fraktalami zagnieżdżonymi na tym samym siatce liczb całkowitych, jeden dla każdego modułu, przez który chcesz go zobaczyć.

Często zadawane pytania

Wypróbuj na żywo

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