Co siedzi w Trójkącie Pascala?

Marek Giebułtowski
IV rok fizyki
Wydział FAIS
Uniwersytet Jagielloński
Kraków 2010
mgiebu@gmail.com

Wstęp

Trójkąt Pascala utworzono, wypełniając  pierwszy wiersz i pierwszą kolumnę macierzy,  jedynkami. Liczbę wpisaną do elementu macierzy k (n, m) oblicza się jako sumę wartości górnej sąsiadki i lewej sąsiadki
k (n, m) = k (n - 1, m) + k (n, m - 1) . Dokonując przekrojów trójkąta lub sumując wartości na danym przekroju, otrzymuje się charakterystyczne ciągi liczbowe. Elementy Trójkąta Pascala są dwumianami Newtona, których podstawowe własności przedstawiono w odpowiedniej sekcji.  W sekcji Cechy Podzielności pokazano jak utworzyć Trójkąt Sierpińskiego z Trójkąta Pascala.

Budujemy macierz kwadratową o wymiarze n×n zawierającą Trójkąt Pascala.
   Do rysowania fraktali przymujemy 200 < n < 500.
   Do przeglądania ciągów najlepiej przyjąć n < 50

n=300;
M=Table[1,{i,1,n,1},{j,1,n,1}];
For [k=2,k≤n,k++,
For[j=2,j≤n,j++,
M[[k,j]]=M[[k-1,j]]+M[[k,j-1]];
]];
For[i=1,i≤n,i++,M[[i,0]]=0];

(* Funkcje dokonujące przekroju *)
kroj[x_, y_, x1_ , y1_,m_]:=Table[M[[x + h  x1,y- h y1]],{h,0,m}];
m2[x_,y_,x1_,y1_]:=Floor[If[((n-x)/x1)<(y/y1),((n-x)/x1),(y/y1)](*+0.5*)];
kro[L_]:=kroj[L[[1]],L[[2]],L[[3]],L[[4]],m2[ L[[1]],L[[2]],L[[3]],L[[4]]]]

For[i=1,i≤n,i++,M[[i,0]]=List];M //MatrixForm  (* Można podejrzeć zawartość *)

For[i=1,i≤n,i++,M[[i,0]]=0];
(* Ale należy wrócić do oznaczeń kolumn, umożliwiających sporządzenie wykresu. *)

Ciągi

Wielomianowe ciągi

Pierwsza kolumna Trójkąta Pascala to wartości funkcji stałej. Z kolumny i-tej  otrzymuje się i+1-szą przez całkowanie dyskretne kolumny i-tej. Całkowanie dyskretne jednomianu stopnia n daje kombinację liniową jednomianów stopnia n i n+1. 
Rząd wiodący drugiej kolumny to funkcja liniowa, trzeciej – kwadratowa.
Aby otrzymać funkcję wielomianu i-tego stopnia należy dobrać odpowiednią kombinacją liniową  kolumn od pierwszej do i+1.

Manipulate [
s=(("Ciąg liczb równoległy do boku trójkąta Pascala ∼x")^(i-1));
If[i==2,s=s"\n Ciąg Arytmetyczny",0];
If[i==3,s=s"\n Liczby Trójkątne",0];
If[i==4,s=s"\n Liczby Piramidalne",0];
DiscretePlot [M[[i,j]],{j,1,n,1},PlotLabel->s]

,{{i,2,"kolumna"},1,n,1}
]
(* otrzymanie ciągów x, (x^2) i (x^(3 ))*) 
L3=Table[ M[[2,i+1]]+6 M[[4,i]],{i,0,n-1,1}];
L2=Table[M[[3,i]]+M[[3,i+1]],{i,0,n-1,1}];
(*
L2[[1]]=L2[[1]]-List;
L3[[1]]=L3[[1]]-6 List;
*)

{"Ciągi jednomianowe", TabView[{M[[2]],{L2},L3}]}

Potęgowe ciągi

Trójąt Pascala podzielono na równoległe przekroje. Wektor (vx,–vy) określa kierunek przekroju. Przekroje rozpoczynają się od elementów M (1,1), (1,2)..., (1,kmax).

Jeśli wysumuje się wartości, w każdym z przekrojów, to otrzyma się szereg  potęgowy w rzędzie wiodącym.

1. Dla (1,1) jest to szereg (2^n)

2. Dla (1,2) jest to ciąg Fibonacciego (((ϕ^n)+(((1-ϕ))^n))/(Sqrt[2])),  gdzie ϕ=(1+(Sqrt[5]))/2

Przekrój dla (1,1) daje rozkład binominalny, który dla kmax dąży do nieskończoności i zbliża się do rozkładu Gaussa.

Manipulate[(* Rysowanie przekrojów *)
LL=Table[kro[{1,i,xv,yv}],{i,1,kmax,1}] ;
Cumul=Table[     Sum[ LL[[i,j]],{j,1,Length[LL[[i]] ]} ]   ,{i,1,Length[ LL ]}];

sL={"Sumy kolejnych przekrojów",
"Przekrój o największej liczbie elementów",
"Przekrój najdalszy od [1,1] skala log","",""};
sL[[5]]=If[ And[xv==1,   yv==1],
sL[[2]]"\n Przybliżenie rozkładu Gaussa"
,
sL[[2]]
];
sL[[4]]=If[ And[xv==1,  yv==2],
sL[[1]]"\n Ciąg Fibonacciego"
,
If[ And[ xv==1 , yv==1],
sL[[1]]"\n Ciąg (2^n) "
,sL[[1]]]
];
part=Min[kmax,25];
Grid[{{
ListLogPlot[Cumul,PlotLabel->sL[[4]],ImageSize->Medium]
,ListPlot[ LL[[kmax]],PlotLabel->sL[[5]],ImageSize->Medium ]
},{ ListLogPlot[LL[[kmax]],PlotLabel->sL[[3]],ImageSize->Medium] 
,{"(Subscript[S, n])=(Subscript[S, n - xv])+(Subscript[S, n - yv]) :"
(*,Partition[Cumul,part ][[1]],"Przekroj:",Partition[LL[[kmax]],part ][[1]]}*)
,Partition[Cumul,Min[Length[Cumul],25]][[1]],"Przekrój:",Partition[LL[[kmax]],Min [Length[LL[[kmax]] ],25 ]  ][[1]]

}
}} 
,Frame->All]
,{xv,1,n,1,2}
,{yv,1,n,1,2}
,{{kmax,n},1,n,1(*,FieldSize->Large*)}

]

Table[Fibonacci[i],{i,1,25}] (* ciąg Fibbonacciego *)

Dwumiany Newtona

Elementy Trójkąta Pascala  mają wartości dwumianu Newtona. Element macierzy M o współrzędnych M(i,j) to dwumian {i+j ; i}. Z macierzy M można odczytać współczynniki rozwinięcia  (((a+b))^n). Poniżej zaprezentowano wybrane właściwości dwumianu Newtona.

Wyrazy M[[i,j]] i M[[j,i]] są równe. Sumowanie dwóch sąsiednich dwumianów mm-1-tego rzędu daje dwumian rzędu mm. Obie właściwości wynikają ze sposobu tworzenia  i symetrii Trójkąta Pascala.

mm=33;
kk=19;
{Sum[Binomial[mm-1,kk-c],{c,0,1,1}]-Binomial[mm,kk]
,Binomial[mm,kk]-Binomial[mm,mm-kk]
}

Suma dwumianów rzędu n jest równa (2^n). Jest to suma wszystkich wyrazów na przeciwprostokątnej. ( Można sprawdzić numerycznie dla trójkąta Pascala w  podsekcji Ciągi potęgowe. )

Sum[Binomial[m,k],{k,0,m}]

Jeśli sumować dwumiany o stałym m, ale ze zmiana znaku dla każdego następnego wyrazu to (poza m = 0) otrzyma się zero. Wynika to stąd, że dwumiany ze znakami naprzemiennymi tworzy się z jednego kompletu dwumianów rzędu n – 1 ze znakiem "–" i jednego kompletu dwumianów rzędu n – 1 ze znakiem "+".

Sum[Binomial[m,k]*(((-1))^k),{k,0,m}]

Istnieją też wzory na sumy dwumianów rzędu n podnoszone do wyższych potęg.

Sum[Binomial[m,k]^2,{k,0,m}]

Sum[Binomial[m,k]^2*(((-1))^k),{k,0,m}]

Sum[Binomial[m,k]^3,{k,0,m}]

Sum[Binomial[m,k]^3*(((-1))^k),{k,0,m}]

Cechy Podzielności

Trójkąt Sierpińskiego można otrzymać przez wybielenie komórek Trójkąta Pascala podzielnych  przez p = 2. Inne warianty fraktali otrzymuje się przez wybielenie komórek podzielnych przez (p = 3, 4, 5...).
Wymiar Fraktalny D Trójkąta  Sierpińskiego można policzyć z wyrażenia (s^D)=(1/N), gdzie s to skala mniejszych trójkątów (w stosunku do obranego dużego trójkąta), a N  liczba mniejszych trójkątów. Dla p = 2 , D=(Subscript[log, 2])3, Dla p = 3 D=(Subscript[log, 3])6. Im ,,dokładniejszy'' model fraktala, tym ,,lepiej'' wypełnia on kwadrat, na którym znajduje się. 
Dla n = 200, p = 2 fraktal wypełnia kwadrat w 86%, a dla n = 1000, p = 2 już w 94%.

{"Numeryczna wartość wymiaru fraktalnego Trójkąta Sierpińskiego",N[Log[3]/Log[2]],N[Log[6]/Log[3]]}

p=2;
For[i=1,i≤n,i++,M[[i,0]]=List];
MM=Mod[M,p] ;
ArrayPlot[MM]

S=0;
For[ii=1,ii≤n,ii++,
For[jj=1,jj≤n ,jj++,
If[MM[[ii,jj]]==0,S++]
]];
Print["Pole modelu fraktalu wynosi ",N[S/(n^2)]," całości"]

ArrayPlot[CellularAutomaton[90,{{1},0},40],PlotLabel->"Inny sposób generowania Trójkąta Sierpińskiego"]

Literatura:

Graham Ronald L, Knuth Donald E., Patashnik Oren, Matematyka konkretna Wydawnictwo Naukowe PWN, Warszawa 2001

http://pl.wikipedia.org/wiki/Tr% C3 % B3jk % C4 %85 t_Pascala

http://pl.wikipedia.org/wiki/Tr% C3 % B3jk % C4 %85 t_Sierpi % C5 %84 skiego

http://reference.wolfram.com/mathematica/guide/Mathematica.html