Pascal-háromszög

A Wikipédiából, a szabad enciklopédiából


\begin{matrix}
&&&&&1\\
&&&&1&&1\\
&&&1&&2&&1\\
&&1&&3&&3&&1\\
&1&&4&&6&&4&&1
\end{matrix}

A Pascal-háromszög első öt sora

A Pascal-háromszög a matematikában a binomiális együtthatók háromszög alakban való elrendezése. A nyugati világ nagy részén Blaise Pascalról nevezték el, noha egyes indiai, perzsa, kínai és itáliai matematikusok már évszázadokkal Pascal előtt tanulmányozták.[1][2]

A háromszögben a sorok számozása zérótól kezdődik, és a páratlan és páros sorokban a számok el vannak csúsztatva egymáshoz képest. A háromszöget a következő egyszerű módon lehet megszerkeszteni: A nulladik sorba csak be kell írni az 1-est. A következő sorok szerkesztésénél a szabály a következő: az új számot úgy kapjuk meg, ha összeadjuk a felette balra és felette jobbra található két számot. Ha az összeg valamelyik tagja hiányzik (sor széle), akkor nullának kell tekinteni. Például az 1-es sor első száma 0 + 1 = 1, míg a 2-es sor középső száma 1 + 1 = 2.

Ez a szerkesztés Pascal képletén alapul, amely szerint

 {n \choose k} = \frac{n!}{k! (n-k)!}

a k-adik binomiális együttható az (x+y)n kifejtésében, akkor

 {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}

bármely nem negatív egész n és bármely 0 és n közötti egész k esetében.[3]

A Pascal-háromszögnek általánosítása három dimenzióra a Pascal-gúla, illetve a többdimenziós általánosítások neve Pascal-szimplex.

A háromszög[szerkesztés | forrásszöveg szerkesztése]

Itt látható a Pascal-háromszög a tizenhatodik sorig:

                                                1
                                             1     1
                                          1     2    1
                                       1     3     3    1
                                    1     4     6     4    1
                                 1     5     10    10    5    1
                              1     6     15    20   15    6     1
                           1     7     21    35    35    21    7    1
                        1     8     28    56    70    56    28    8    1
                     1     9     36    84    126   126   84    36    9    1
                  1     10    45    120   210   252   210   120   45    10   1
               1     11    55   165   330    462   462   330   165   55    11  1
            1     12    66    220   495   792   924   792   495   220   66    12  1
         1     13    78   286   715   1287  1716  1716  1287   715   286   78    13  1
      1    14     91   364   1001  2002  3003  3432  3003  2002  1001   364   91    14  1
   1    15    105   455   1365  3003  5005  6435  6435  5005  3003  1365  455   105    15  1
1    16   120    560   1820  4368  8008  11440 12870 11440  8008  4368  1820  560   120  16   1


A Pascal-háromszög és a binomiális kifejtés[szerkesztés | forrásszöveg szerkesztése]

A Pascal-háromszög megadja a binomiális kifejtés együtthatóit. Például tekintsük a

(x + y)2 = x2 + 2xy + y2 = 1x2y0 + 2x1y1 + 1x0y2.

kifejtést. Látható, hogy az együtthatók a Pascal-háromszög kettes sorában találhatók: 1, 2, 1.

Általános esetben ha az x + y alakú binomot egész hatványra emeljük, akkor:

(x + y)n = a0xn + a1xn‒1y + a2xn‒2y2 + … + an‒1xyn‒1 + anyn,

ahol a kifejtés ai együtthatói éppen a Pascal-háromszög n-es sorában található számok. Más szóval

a_i = {n \choose i}.

Ez a binomiális tétel.

Megfigyelhető, hogy a Pascal-háromszög teljes jobb oldali átlója megfelel az yn együtthatójának, a következő átló az xyn-1 együtthatója és így tovább.

A binomiális tételnek és a Pascal-háromszög megszerkesztésének kapcsolatához tekintsük meg, hogyan lehet kiszámítani az (x + 1)n+1 kifejtésének az együtthatóit az (x + 1)n együtthatói alapján. (Az egyszerűség kedvéért legyen y = 1). Tételezzük fel, hogy

(x+1)^n=\sum_{i=0}^n a_i x^i.

Akkor

(x+1)^{n+1} = (x+1)(x+1)^n = x(x+1)^n + (x+1)^n = \sum_{i=0}^n a_i x^{i+1} + \sum_{i=0}^n a_i x^i.

A két összeget a következőképpen lehet átrendezni:

\sum_{i=0}^{n} a_{i} x^{i+1} + \sum_{i=0}^n a_i x^i =
\sum_{i=1}^{n+1} a_{i-1} x^{i} + \sum_{i=0}^n a_i x^i =
\sum_{i=1}^{n} a_{i-1} x^{i} + \sum_{i=1}^n a_i x^i + a_0x^0 + a_{n}x^{n+1} =
\sum_{i=1}^{n} (a_{i-1} + a_i)x^{i} + a_0x^0 + a_{n}x^{n+1} =
\sum_{i=1}^{n} (a_{i-1} + a_i)x^{i} + x^0 + x^{n+1} (mivel a0 = an = 1)

Így most megkaptuk az (x + 1)n+1 polinom kifejtését az (x + 1)n együtthatóinak függvényében (ezek az ai-k), és pont erre van szükség, ha ki akarjuk számítani az egyik sort a felette levő sor tagjainak segítségével.

Ismétlésül:

  • az átlók minden tagja a bal felsőtől indulva a jobb alsóig x azonos hatványának felel meg, * az a-tagok az (x + 1)n polinom együtthatói
  • és az (x + 1)n+1 együtthatóit kell meghatároznunk.

Így minden i esetében, amely nem 0 és nem n + 1, az xi tag együtthatója az (x + 1)n+1 polinomban egyenlő ai-(ez a meghatározandó számhoz képest balra fent van) + ai‒1 (ez pedig az előzőtől rögtön jobbra). Ez pedig pont a Pascal-háromszög soronkénti szerkesztésének egyszerű szabálya.

Ez az érvelés könnyen átalakítható a binomiális tétel matematikai bizonyításává a teljes indukció módszerével.

A binomiális tétel érdekes következményét kapjuk, ha mindkét változó, x és y értékét 1-nek vesszük. Ekkor tudjuk, hogy  (1+1)^n = 2^n , és így

 {n \choose 0} + {n \choose 1} + \cdots +{n \choose n-1} + {n \choose n} = 2^n.

Más szóval, a Pascal-háromszög n-edik sorában a tagok összege 2 n-edik hatványa.

Kombinációk[szerkesztés | forrásszöveg szerkesztése]

A Pascal-háromszög egy másik alkalmazása a kombinációk kiszámítása. Például n elem k elemű kombinációinak száma

 \mathbf{C}(n,k) = \mathbf{C}_k^n= {_nC_k} = {n \choose k} = \frac{n!}{k!(n-k)!}.

Ez éppen a Pascal-háromszög elemeinek képlete. Hogyha adva van a Pascal-háromszög, akkor a számítás helyett elég ránézni a megfelelő elemre. Például egy 10 tagú kosárlabdacsapatból kiválasztunk 8 tagot. A választ a 10. sor 8. eleme adja meg: 45.

Tulajdonságok[szerkesztés | forrásszöveg szerkesztése]

A sorok[szerkesztés | forrásszöveg szerkesztése]

  • Egy sor elemeinek összege kétszerese az előző sor összegének. A nulladik sor összege egy, ami éppen 20. Továbbá, az első sor összege 21 = 2, a másodiké 22 = 4, és így tovább, az n-edik sor összege 2n.
  • Az összeg helyett a szorzatokat véve egy olyan sorozatot kapunk (Sloane A001142), ami kapcsolódik az e számhoz.[4][5]

Tehát a sorozat így definiálható:

s_n=\prod_{k=0}^{n}\binom{n}{k} = \prod_{k=0}^{n}\frac{n!}{k!(n-k)!}~, ~ n \geq 0.

Az egymást követő tagok hányadosa:

\frac{s_{n+1}}{s_{n}}=\frac{(n+1)!^{(n+2)}\prod_{k=0}^{n+1}{k!^{-2}}}{n!^{(n+1)}\prod_{k=0}^{n}{k!^{-2}}}
=\frac{(n+1)^n}{n!}

aminek hányadosa:

\frac{(s_{n+1})(s_{n-1})}{(s_n)^2}=\left(\frac{n+1}{n}\right)^n, ~ n\geq 1.

A fenti egyenlet jobb oldaláról tudjuk, hogy az e-hez tart:

\textit{e} =\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^{n}.
  • Ha minden helyet helyi értéknek tekintünk, akkor az egyes sorokat számokként összeolvasva a 10-es átlépésig 11 hatványait kapjuk. Az ez után következő soroknál átvitel képződik, amit átvive 11 további hatványai adódnak. Magasabb alapú számrendszerben az adott alapszámnál eggyel nagyobb szám hatványai tovább olvashatók le a Pascal-háromszögben az adott számrendszerben, de az összefüggés átvitellel minden számrendszerre teljesül.
Hármas számrendszerben: 1 2 13 = 42 (16)
⟨1, 3, 3, 1⟩ → 2 1 0 13 = 43 (64)
Kilences számrendszerben: 1 2 19 = 102 (100)
1 3 3 19 = 103 (1000)
⟨1, 5, 10, 10, 5, 1⟩ → 1 6 2 1 5 19 = 105 (100000)
  • Egyes számok kapcsolódnak a Lozanić-háromszöghöz.
  • Az n-edik sorban levő számok négyzetösszege megegyezik a 2n-edik sor középső elemével. Például:
12 + 42 + 62 + 42 + 12 = 70.
Általában:
\sum_{k=0}^n {n \choose k}^2 = {2n \choose n}.
  • Ha n páros, akkor a középső termből kivonva a két balra levő termet egy Catalan-számot kapunk, mégpedig az (n/2 + 1)-edik Catalan-számot. Például a negyedik sorban 6 − 1 = 5, ami a harmadik Catalan-szám, és 4/2 + 1 = 3.
  • Hogyha n = p prímszám, akkor az 1-esek kivételével a sor minden eleme osztható p-vel. Ez könnyen bizonyítható, mivel a prímszámoknak nincs valódi osztója. A háromszögben minden szám egész, így (p-k)! és k! osztója p!\,-nak. A nevezőben viszont nem található p, így az osztás elvégzésekor nem fog kiesni a számlálóból.
  • Paritás: Számoljuk meg az n-edik sorban a páratlan számokat. Jelölje x n kettes számrendszerbeli alakjában az 1-esek számát. Ekkor a páratlan számok száma a sorban megegyezik 2x-szel.[6]
  • Polaritás: Az egy sorban álló számokat váltakozó előjellel összeadva nullát kapunk.

Az átlók[szerkesztés | forrásszöveg szerkesztése]

Egyes egyszerű minták ránézésre is nyilvánvalóak a Pascal-háromszög átlóiban:

  • A bal és jobb oldali átlók csak 1-eseket tartalmaznak.
  • Balról és jobbról a második átlók sorrendben tartalmazzák a természetes számokat.
  • Befelé haladva, a következő átlók a tetraéderszámokat tartalmazzák.
  • Általában is igaz, hogy az átlópárok a d-dimenziós háromszögszámokat tartalmazzák. Ezeket képlettel a következőképpen lehet leírni:
 \textrm{tri}_1(n) = n \quad\mbox{és}\quad \textrm{tri}_{d}(n) = \sum_{i=1}^n \mathrm{tri}_{d-1}(i).

Más képlet:

\textrm{tri}_d(n)=\begin{cases} 1 & \mbox{ha } d=0 \\ n & \mbox{ha } d=1 \\ \displaystyle \frac{1}{d!}\prod_{k=0}^{d-1} (n+k) & \mbox{ha } d\ge 2\end{cases}

Rekurzió nélkül:

\operatorname{tri}_d(n)=\frac{1}{d!}\prod_{k=0}^{d-1} (n+k) = {n^{(d)}\over d!} = \binom{n+d-1}{d}
ahol n(d) a Pochhammer-szimbólum.

A trid függvény mértani értelmezése: minden d esetén trid(1) = 1. Szerkesszünk egy d-dimenziós háromszöget oly módon, hogy az előző alakzat alá minden pont alá még egy pontot helyezünk el, amely az trid(1) = 1-nek felel meg. Ezeket az új pontokat a Pascal-háromszöghöz hasonló módon helyezzük el. A trid(x) értékének meghatározásához: x pont alkotja a sokszöget. trid(x) egyenlő a d-dimenziós háromszögben található pontok számával. Egy 1-dimenziós háromszög csak egy sor, így tri1(x) = x, amely a természetes számok sorozata. A pontok száma mindegyik rétegben trid ‒ 1(x) -nak felel meg.

Egy sor vagy oszlop kiszámítása[szerkesztés | forrásszöveg szerkesztése]

Az egyes sorok és átlók egyszerű algoritmusokkal számolhatók, amelyek nem igénylik a faktoriálisokat vagy az előző sorokat.

Az n-edik sor kiszámítása: Az első elem az 1. A további elemek az előzőből egy törttel való szorzással állnak elő:

 {n\choose k}= {n\choose k-1}\times \frac{n+1-k}{k}.

Például az ötödik sor:\tfrac{5}{1}\tfrac{4}{2}\tfrac{3}{3}\tfrac{2}{4} és \tfrac{1}{5}, így az elemek \tbinom{5}{0}=1,   \tbinom{5}{1}=1\times\tfrac{5}{1}=5,   \tbinom{5}{2}=5\times\tfrac{4}{2}=10. A további elemek a szimmetria tulajdonság alapján az előbbiek tükörképei.

Az \tbinom{n}{0}, \tbinom{n+1}{1}, \tbinom{n+2}{2}, ... elemeket tartalmazó átló kiszámítására újra \tbinom{n}{0}=1-gyel kezdünk, és a további elemek a

 {n+k\choose k}= {n+k-1\choose k-1}\times \frac{n+k}{k}

törtekkel való szorzással kaphatók.

Például az \tbinom{5}{0}-val kezdődő átlón a törtek:   \tfrac{6}{1}\tfrac{7}{2}\tfrac{8}{3}, ..., így az elemek \tbinom{5}{0}=1,   \tbinom{6}{1}=1\times\tfrac{6}{1}=6,   \tbinom{7}{2}=6\times\tfrac{7}{2}=21. A további elemek a szimmetria tulajdonság miatt az előzőek tükörképei.

Egyéb mintázatok és tulajdonságok[szerkesztés | forrásszöveg szerkesztése]

Sierpiński-háromszög
  • Az a minta, amelyet akkor kapunk, ha a Pascal-háromszögben a páratlan számokat kiszínezzük, a Sierpiński-háromszögnek nevezett fraktálra emlékeztet, és ez a hasonlóság annál erősebb, minél több sort veszünk figyelembe. Határértékben, ha a sorok száma tart a végtelenhez, az így létrejövő minta maga a Sierpiński-háromszög. Ha a számok közül a 3, 4 stb. többszöröseit színezzük ki, egyéb mintázatokat kapunk.
A különböző utak száma, ha csak jobbra és lefelé szabad mozogni
  • Képzeljük el, hogy a háromszögben minden szám csomópont egy hálózatban, összekötve az alatta és felette levő sorban található szomszédos számokkal. Most számoljuk meg minden csomóponthoz az utak számát, amely a legfelső ponthoz vezet – ez éppen a csomópontban található Pascal-szám lesz.
Pascal's Triangle 4 paths.svg
  • Egy további tulajdonság akkor válik nyilvánvalóvá, ha a háromszög sorait balra igazítjuk. Ekkor az átlók összegei a Fibonacci-számok találhatók, amelyeket alább a színes átlók mutatnak:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1

A Pascal háromszög tükrözése és a kölcsönösen megfeleltetett számok szorzata[szerkesztés | forrásszöveg szerkesztése]

  • Egy példa: (OEIS) A129352 Number parallelogram based on Pascal's triangle (and special mirror of central and multiply of diagonal). http://oeis.org/A129352

Táblázat a fenti OEIS példához hasonlóan[szerkesztés | forrásszöveg szerkesztése]

fix pont: karakterek száma: "0" 1 2 3 4 5 6 7 8 9 10 11 12 összesen
12 0 vagy AAAAAAAAAAAA 924 924
11 1 vagy AAAAAAAAAAAB 462 462 924
10 2 vagy AAAAAAAAAABB 210 504 210 924
9 3 vagy AAAAAAAAABBB 84 378 378 84 924
8 4 vagy AAAAAAAABBBB 28 224 420 224 28 924
7 5 vagy AAAAAAABBBBB 7 105 350 350 105 7 924
6 6 vagy AAAAAABBBBBB 1 36 225 400 225 36 1 924
5 7 vagy AAAAABBBBBBB 7 105 350 350 105 7 924
4 8 vagy AAAABBBBBBBB 28 224 420 224 28 924
3 9 vagy AAABBBBBBBBB 84 378 378 84 924
2 10 vagy AABBBBBBBBBB 210 504 210 924
1 11 vagy ABBBBBBBBBBB 462 462 924
0 12 vagy BBBBBBBBBBBB 924 924

A fenti táblázat binomiális együtthatókkal[szerkesztés | forrásszöveg szerkesztése]

fix pont: karakterek száma: "0" 1 2 3 4 5 6 7 8 9 10 11 12 össz.
12 0 vagy AAAAAAAAAAAA C(0,0)*C(12,6) 924
11 1 vagy AAAAAAAAAAAB C(1,0)*C(11,6) C(1,1)*C(11,5) 924
10 2 vagy AAAAAAAAAABB C(2,0)*C(10,6) C(2,1)*C(10,5 C(2,2)*C(10,4) 924
9 3 vagy AAAAAAAAABBB C(3,0)*C(9,6) C(3,1)*C(9,5) C(3,2)*C(9,4) C(3,3)*C(9,3) 924
8 4 vagy AAAAAAAABBBB C(4,0)*C(8,6) C(4,1)*C(8,5) C(4,2)*C(8,4) C(4,3)*C(8,3) C(4,4)*C(8,2) 924
7 5 vagy AAAAAAABBBBB C(5,0)*C(7,6) C(5,1)*C(7,5) C(5,2)*C(7,4) C(5,3)*C(7,3) C(5,4)*C(7,2) C(5,5)*C(7,1) 924
6 6 vagy AAAAAABBBBBB C(6,0)*C(6,6) C(6,1)*C(6,5) C(6,2)*C(6,4) C(6,3)*C(6,3) C(6,4)*C(6,2) C(6,5)*C(6,1) C(6,6)*C(6,0) 924
5 7 vagy AAAAABBBBBBB C(7,1)*C(5,5) C(7,2)*C(5,4) C(7,3)*C(5,3) C(7,4)*C(5,2) C(7,5)*C(5,1) C(7,6)*C(5,0) 924
4 8 vagy AAAABBBBBBBB C(8,2)*C(4,4) C(8,3)*C(4,3) C(8,4)*C(4,2) C(8,5)*C(4,1) C(8,6)*C(4,0) 924
3 9 vagy AAABBBBBBBBB C(9,3)*C(3,3) C(9,4)*C(3,2) C(9,5)*C(3,1) C(9,6)*C(3,0) 924
2 10 vagy AABBBBBBBBBB C(10,4)*C(2,2) C(10,5)*C(2,1) C(10,6)*C(2,0) 924
1 11 vagy ABBBBBBBBBBB C(11,5)*C(1,1) C(11,6)*C(1,0) 924
0 12 vagy BBBBBBBBBBBB C(12,6)*C(0,0) 924

A táblázat soraiban levő számok értelmezése[szerkesztés | forrásszöveg szerkesztése]

Hat darab "A" és hat darab "B" objektum (AAAAAABBBBBB), (karakter) összes permutációját vessük össze a kiindulási Hat darab "A" és hat darab "B" objektum (AAAAAABBBBBB)kiindulási mintájával és vizsgáljuk meg, hogy mennyi fixpontot kapunk!

Sorra nulla, egy, kettő, … öt, tíz, tizenegy, és tizenkettő fixpont lehet. Ezeknek a darabszámát adja meg a táblázat:

6 6 vagy AAAAAABBBBBB sor :1 36 225 400 225 36 1 a fixpontok száma, ez összesen 924

Ha az összes permutációt összevetjük hasonlóképpen 12 db "A" karakterrel(AAAAAAAAAAAA), vagy 12 db "B" karakterrel (BBBBBBBBBBBB),akkor csak hat fixpont lehet a legfelső és legalsó táblázatsor szerint: 924 darab.

Értelemszerűen a táblázat további sorai is a fixpontok számát írják le.

"Fixpont" alatt az összehasonlítás során az azonos helyen megegyező karakter értendő!

lásd:

http://en.wikipedia.org/wiki/Rencontres_numbers

http://en.wikipedia.org/wiki/Cycles_and_fixed_points

http://en.wikipedia.org/wiki/Subfactorial

Még kifinomultabb minták[szerkesztés | forrásszöveg szerkesztése]

Vannak további meglepő, kifinomult minták is. A háromszög egy pontjából egy elnyújtott átlót képezünk úgy, hogy minden elemtől lépünk egyet jobbra és utána egyet jobbra-le, vagy ugyanezt ellenkező irányban. Ilyen például az 1, 6, 5, 1 tagokból álló vonal, amely az 1, 3, 3, 1 sorban kezdődik és három sorral lejjebb végződik. Egy ilyen "átló" tagjainak összege Fibonacci-szám. A példában ez a Fibonacci-szám 13:

                                       1
                                    1     1
                                 1     2     1
                              1  →  3 ↓   3     1
                           1     4    6  →  4 ↓   1
                        1     5     10    10   5  →  1 ↓
                     1  →  6 ↓   15    20    15    6    1
                   1     7    21    35    35    21    7     1
                1     8     28    56    70    56    28    8     1
              1     9     36    84    126   126   84    36    9     1
            1     10    45    120   210   252   210   120   45    10    1
          1     11    55    165   330   462   462   330   165   55    11    1
        1     12    66    220   495   792   924   792   495   220   66    12    1
      1     13    78    286   715   1287  1716  1716  1287  715   286   78    13    1
    1    14     91   364   1001  2002  3003  3432  3003  2002  1001   364   91    14    1
  1    15   105   455   1365   3003  5005  6435  6435  5005  3003  1365  455   105   15    1
1    16  120   560   1820  4368  8008 11440 12870 11440  8008  4368  1820   560   120   16   1

A második megjelölt átló tagjainak összege 233. A jobbra illetve jobbra-le lépések között „kiugrott” számok összege szintén Fibonacci-szám. Például az első átlónál kiugrott számok 3, 4 és 1, amelyeknek az összege 8.

Továbbá, ha m-el jelöljük az (n+1)-edik sort, akkor az m-edik sor tagjainak négyzetösszege egyenlő a (2m-1) -edik sor középső tagjával. Például 1^2 + 4^2 + 6^2 + 4 ^2 + 1^2 = 70. Általánosságban:

\sum_{k=0}^n {n \choose k}^2 = {2n \choose n}

Másik érdekes minta, hogy bármely páratlan m esetében, az m-edik sor középső tagja mínusz a kettővel balra levő tag Catalan-szám, pontosabban a (m + 1)/2 Catalan-szám. Például az 5-ös sorban 6 ‒ 1 = 5, ami a 3-adik Catalan-szám és (5 + 1)/2 = 3.

Ezen kívül, az m sor tagjainak összege 2m‒1. Például az 5-ös sor tagjainak összege 1 + 4 + 6 + 4 + 1 = 16, amely 2^4 = 16. Ez a binomiális tételből következik, ha az (1 + 1)m‒1-re alkalmazzuk.

A Pascal-háromszög még egy érdekes tulajdonsága, hogy azokban a sorokban, ahol a második szám prímszám, a sorban található minden szám (az 1-esek kivételével) ennek a prímnek a többszöröse.

Binomiális mátrix mint hatványmátrix. A pontok 0-t jelentenek.

Mátrixhatvány[szerkesztés | forrásszöveg szerkesztése]

Mivel faktoriálisokból épül fel, a Pascal-háromszög felírható mátrixhatványként: a Pascal-háromszög annak a mátrixnak a hatványa, amely 1, 2, 3, 4, … számokat tartalmazza a főátló alatt, az összes többi eleme pedig nulla.

A politópok elemeinek száma[szerkesztés | forrásszöveg szerkesztése]

A Pascal-háromszög használható politópok elemeinek számának meghatározásához.

Például a harmadik sor 1, 3, 3, 1. Egy két dimenziós szimplex (háromszög) 2 dimenziós eleme önmaga, három oldala 1 dimenziós szimplex, három csúcsa három 0 dimenziós szimplex, és az üres halmaz egy -1 dimenziós szimplex. Hasonlóan, a tetraéder elemeinek száma is rendre 1, 4, 6, 4, 1. Magasabb dimenziós szimplexek elemeinek száma is megadható hasonló módon.

Ezt bizonyíthatjuk is, ha meggondoljuk, hogy hogyan lehet kiszámítani a szimplex adott dimenziós elemeinek számát az alap elemeinek számából. Ugyanis, ha tekintjük a konstrukciót, akkor például tetraéder esetén a háromszögnek 0 téreleme van, de keletkezik egy új. A lapok száma 1 + 3, az alap és az alap síkjára nem illeszkedő csúcs és az alap oldalai által kifeszített háromszögek. Az élek száma 3 + 3, az alap élei és az alap csúcsait az új csúccsal összekötő élek. A csúcsok száma 3 + 1, az alap csúcsai és az újonnan felvett csúcs, amelynek metszete az alappal üres. Ez megmagyarázza az üres elem felvételét. Végül az új szimplexhez is hozzávesszük az üres elemet.

A négyzetekhez hasonló minta konstruálható. A megfelelő számok egy Pascal-háromszöghöz hasonlóan képzett számháromszögből olvashatók le. amiben (x + 2)n együtthatói szerepelnek (x + 1)n együtthatói helyett. Az első két sor: a nulladik sorban 1 áll, az első sorban 1, 2. A többi elem az

 {n \choose k} = 2\times{n-1 \choose k-1} + {n-1 \choose k}

szabály alapján képezhető. Szavakkal: a bal felső elem kétszereséhez adjuk a jobb elemet.

Az így kapott háromszög első néhány sora:

                             1
                         1       2
                     1       4       4
                 1       6       12      8
             1       8       24      32      16
         1       10      40      80      80       32
     1       12      60      160     240     192       64
 1       14      84      280     560     672      448       128

Ez a háromszög megkapható úgy is, hogy a Pascal-háromszög elemeit megszorozzuk 2k-nal, ahol k az adott szám pozíciója a sorban. Ebből a háromszögből a szimplexek helyett a kockák, illetve hiperkockák d dimenziós elemeinek száma olvasható le. Például egy két dimenziós kocka ([négyzet]]) két dimenziós elemeinek száma 1, 1 dimenziós elemeinek (oldalainak) száma 4, és 0 dimenziós elemeinek (csúcsainak) száma szintén 4. Ebben a táblázatban nem szerepel az üres elem. A kocka elemeinek száma rendre 1, 6, 12 és 8. Ez a mintázat a végtelenségig ismétlődik.

A mögöttes konstrukciós elv ez: Vegyük a kockát, és toljuk el élhossznyira a hipersíkjára merőlegesen. Az ezeket összekötő szakaszokkal együtt meghatároznak egy eggyel magasabb dimenziós kockát, amit itt most nevezzünk hiperkockának. A két kocka miatt a kocka elemei megduplázódnak, emiatt kell a bal elemet kettővel szorozni. Az új elemek a szimplexhez hasonlóan keletkeznek, azzal az eltéréssel, hogy nem keletkeznek új csúcsok, emiatt nem kell számításba venni az üres elemet.

Ebben a háromszögben az m-edik sorban az elemek összege 3m − 1. Például az ötödik sorban 1 + 8 + 24 + 32 + 16 = 81, ami éppen 3^4.

sin(x)n+1/x Fourier-transzformációja[szerkesztés | forrásszöveg szerkesztése]

Ahogy a fentiekben írtuk, az n-edik sor az (x + 1)n együtthatóit tartalmazza. Az (x − 1)n együtthatói előjel nélkül ugyanezek, előjelesen pedig váltakozva pozitív és negatív előjelűek. Normalizálás után ugyanezek a számok jelennek meg sin(x)n+1/x Fourier-együtthatóiként. Pontosabban: ha n páros, akkor vegyük a valós részt, ha páratlan, akkor a képzetes részt. Ekkor az eredmény egy lépcsős függvény, amelynek értékei normalizálás után a háromszög n-edik sorában álló számok váltakozó előjellel. [7]

Például, a

\,\mathfrak{Re}\left(\text{Fourier} \left[  \frac{\sin(x)^5}{x}   \right]\right)

függvényből kapott lépcsős függvény együtthatói előjel nélkül a háromszög 4. sorában találhatók. A villamosmérnökök által gyakran használt eset:

\,\mathfrak{Re}\left(\text{Fourier} \left[ \frac{\sin(x)^1}{x}\right] \right)

egy négyszögjel.[8] Ennek a háromszögben a nulladik sor felel meg, ami egyetlen egyesből áll.

Ha n 4-gyel osztva 2-t vagy 3-at ad maradékul, akkor az n-edik sor -1-gyel kezdődik. Az első elemek sorozata a képzetes egység ciklikusan ismétlődő hatványainak felel meg:

 \, +i,-1,-i,+1,+i,\ldots \,

Sejtautomaták[szerkesztés | forrásszöveg szerkesztése]

Az egy dimenziós életjáték az időben Pascal-háromszögre (modulo 2), illetve Sierpinski-háromszögre emlékeztető alakzatokat formál a 60-as szabállyal, ahol a fekete sejtek a páratlan számoknak felelnek meg.[9] A 102-es szabállyal ugyanezek az alakzatok jelennek meg, hogyha eltekintünk a vezető nulláktól. A 90-es szabály szintén ilyen alakzatokat állít elő, de az alakzat minden sejtjét egy fekete (halott) sejt választja el.

Kiterjesztések[szerkesztés | forrásszöveg szerkesztése]

A Pascal-háromszög a negatív számokkal jelzett sorokra is kiterjeszthető:

Először is írjuk fel a háromszöget a következő alakban:


m = 0 m = 1 m = 2 m = 3 m = 4 m = 5 ...
n = 0 1 0 0 0 0 0 ...
n = 1 1 1 0 0 0 0 ...
n = 2 1 2 1 0 0 0 ...
n = 3 1 3 3 1 0 0 ...
n = 4 1 4 6 4 1 0 ...

Terjesszük ki az 1-esek oszlopát a negatív irányba:

m = 0 m = 1 m = 2 m = 3 m = 4 m = 5 ...
n = −4 1 ...
n = −3 1 ...
n = −2 1 ...
n = −1 1 ...
n = 0 1 0 0 0 0 0 ...
n = 1 1 1 0 0 0 0 ...
n = 2 1 2 1 0 0 0 ...
n = 3 1 3 3 1 0 0 ...
n = 4 1 4 6 4 1 0 ...

Tudjuk, hogy:

 {n \choose m} = {n-1 \choose m-1} + {n-1 \choose m}

ami átrendezhető a következő alakba:

 {n-1 \choose m} = {n \choose m} - {n-1 \choose m-1}

így a negatív sorokban álló többi szám is számítható:

m = 0 m = 1 m = 2 m = 3 m = 4 m = 5 ...
n = −4 1 −4 10 −20 35 −56 ...
n = −3 1 −3 6 −10 15 −21 ...
n = −2 1 −2 3 −4 5 −6 ...
n = −1 1 −1 1 −1 1 −1 ...
n = 0 1 0 0 0 0 0 ...
n = 1 1 1 0 0 0 0 ...
n = 2 1 2 1 0 0 0 ...
n = 3 1 3 3 1 0 0 ...
n = 4 1 4 6 4 1 0 ...

Ez a kiterjesztés megőrzi azt a tulajdonságot, hogy az m-edik oszlop n függvényeként az


{n \choose m} = \frac{1}{m!}\prod_{k=0}^{m-1} (n-k) = \frac{1}{m!}\prod_{k=1}^{m} (n-k+1)

polinom együtthatói.

Továbbá az n-edik sorban (1 + x)n együtthatói állnak:


(1+x)^n = \sum_{k=0}^\infty {n \choose k} x^k \quad |x| < 1

Például:


(1+x)^{-2} = 1-2x+3x^2-4x^3+\cdots \quad |x| < 1

Sorozatként tekintve a negatív sorok divergálnak, azonban még mindig Abel-összegezhetők maradnak, és Abel-összegük 2n. Az n = -1 sorozat a Grandi-sorozat, amelynek Abel-összege 1/2, és n = -2 számú sor éppen az 1 − 2 + 3 − 4 + · · ·, aminek Abel-összege 1/4.

A kiterjesztés másik módja a másik átló egyeseit folytatja:


m = −4 m = −3 m = −2 m = −1 m = 0 m = 1 m = 2 m = 3 m = 4 m = 5 ...
n = −4 1 0 0 0 0 0 0 0 0 0 ...
n = −3 1 0 0 0 0 0 0 0 0 ...
n = −2 1 0 0 0 0 0 0 0 ...
n = −1 1 0 0 0 0 0 0 ...
n = 0 0 0 0 0 1 0 0 0 0 0 ...
n = 1 0 0 0 0 1 1 0 0 0 0 ...
n = 2 0 0 0 0 1 2 1 0 0 0 ...
n = 3 0 0 0 0 1 3 3 1 0 0 ...
n = 4 0 0 0 0 1 4 6 4 1 0 ...

A kiterjesztés másik módja a másik átló egyeseit folytatja:


m = −4 m = −3 m = −2 m = −1 m = 0 m = 1 m = 2 m = 3 m = 4 m = 5 ...
n = −4 1 0 0 0 0 0 0 0 0 0 ...
n = −3 1 0 0 0 0 0 0 0 0 ...
n = −2 1 0 0 0 0 0 0 0 ...
n = −1 1 0 0 0 0 0 0 ...
n = 0 0 0 0 0 1 0 0 0 0 0 ...
n = 1 0 0 0 0 1 1 0 0 0 0 ...
n = 2 0 0 0 0 1 2 1 0 0 0 ...
n = 3 0 0 0 0 1 3 3 1 0 0 ...
n = 4 0 0 0 0 1 4 6 4 1 0 ...

Újra a fenti szabállyal:

m = −4 m = −3 m = −2 m = −1 m = 0 m = 1 m = 2 m = 3 m = 4 m = 5 ...
n = −4 1 0 0 0 0 0 0 0 0 0 ...
n = −3 −3 1 0 0 0 0 0 0 0 0 ...
n = −2 3 −2 1 0 0 0 0 0 0 0 ...
n = −1 −1 1 −1 1 0 0 0 0 0 0 ..
n = 0 0 0 0 0 1 0 0 0 0 0 ...
n = 1 0 0 0 0 1 1 0 0 0 0 ...
n = 2 0 0 0 0 1 2 1 0 0 0 ...
n = 3 0 0 0 0 1 3 3 1 0 0 ...
n = 4 0 0 0 0 1 4 6 4 1 0 ...

Ez a kiterjesztés megőrzi a mátrixhatvány tulajdonságot, vagyis:


\exp\begin{pmatrix}
. & . & . & . & . \\
1 & . & . & . & . \\
. & 2 & . & . & . \\
. & . & 3 & . & . \\
. & . & . & 4 & .
\end{pmatrix} =
\begin{pmatrix}
1 & . & . & . & . \\
1 & 1 & . & . & . \\
1 & 2 & 1 & . & . \\
1 & 3 & 3 & 1 & . \\
1 & 4 & 6 & 4 & 1
\end{pmatrix},

folytatása:



\exp\begin{pmatrix}
. & . & . & . & . & . & . & . & . & . \\
-4 & . & . & . & . & . & . & . & . & . \\
. & -3 & . & . & . & . & . & . & . & . \\
. & . & -2 & . & . & . & . & . & . & . \\
. & . & . & -1 & . & . & . & . & . & . \\
. & . & . & . & 0 & . & . & . & . & . \\
. & . & . & . & . & 1 & . & . & . & . \\
. & . & . & . & . & . & 2 & . & . & . \\
. & . & . & . & . & . & . & 3 & . & . \\
. & . & . & . & . & . & . & . & 4 & .
\end{pmatrix} =
\begin{pmatrix}
1 & . & . & . & . & . & . & . & . & . \\
-4 & 1 & . & . & . & . & . & . & . & . \\
6 & -3 & 1 & . & . & . & . & . & . & . \\
-4 & 3 & -2 & 1 & . & . & . & . & . & . \\
1 & -1 & 1 & -1 & 1 & . & . & . & . & . \\
. & . & . & . & . & 1 & . & . & . & . \\
. & . & . & . & . & 1 & 1 & . & . & . \\
. & . & . & . & . & 1 & 2 & 1 & . & . \\
. & . & . & . & . & 1 & 3 & 3 & 1 & . \\
. & . & . & . & . & 1 & 4 & 6 & 4 & 1
\end{pmatrix}

A kiterjesztés megőrzi a fent leírt Fibonacci-összeg tulajdonságot a negatív indexekre is.

Mindkét kiterjesztés értelmezhető a gammafüggvény felhasználásával:

 {n \choose k} = \frac{n!}{(n-k)! k!} \equiv \frac{\Gamma(n+1)}{\Gamma(n-k+1)\Gamma(k+1)}

és a \Gamma(z) gammafüggvény bizonyos határértékeit véve.

Történet[szerkesztés | forrásszöveg szerkesztése]

A Yang Hui-háromszög kínai ábrázolása

A binomiális együtthatók háromszögbe rendezésének legkorábbi ábrázolása a 10. században bukkant fel, a Chandas Shastra című ókori indiai könyvhöz írott kommentárokban. Az ókori szanszkrit nyelvű könyvet Pingala írta valamikor a Kr. e. 5. és 2. század között, de ez csak töredékesen maradt fenn. A könyvet kommentáló Halayudha 975 körül arra használta a háromszöget, hogy a Meru-prastaara-ra vagyis a Moru-hegy lépcsőire tett homályos utalásokat megmagyarázza. Arra is felfigyelt, hogy a „ferde” átlók tagjainak összege a Fibonacci-számokat adja. Később Bhattotpala indiai matematikus (1068 körül) megadta a háromszög sorait 0-tól 16-ig.

Ugyanebben az időben Perzsiában is tárgyalták Al-Karadzsi matematikus (953–1029) és Omar Khajjám költő-csillagász-matematikus (1048-1131); ezért a háromszöget Iránban „Khajjám-háromszög” néven ismerik. A háromszöghöz kapcsolódóan több tételt is ismertek, köztük a binomiális tételt.

A 13. században Yang Hui (1238-1298) bemutatta a számtani háromszöget, amely azonos volt a Pascal-háromszöggel. A háromszöget Kínában „Yang Hui-háromszög” néven ismerik.

Végül pedig Olaszországban „Tartaglia-háromszög” a neve, Niccolò Tartaglia matematikusról, aki egy évszázaddal Pascal előtt élt. Tartagliának tulajdonítják a harmadfokú egyenlet megoldását.

1655-ben Blaise Pascal a Traité du triangle arithmétique című értekezésében összegyűjtötte a háromszögre vonatkozó akkor ismert adatokat és valószínűség-számítási feladatok megoldására használta. A háromszöget utóbb Pierre Raymond de Montmort (1708) és Abraham de Moivre (1730) nevezte el Pascalról.

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

  1. [1]
  2. Pascal’s Triangle by Andrew Samuels
  3. Negativ vagy n-nél nagyobb k esetében a binomiális együttható értékét nullának tekintjük.
  4. Brothers, H. J. (2012), "Finding e in Pascal’s triangle", Mathematics Magazine 85: 51, DOI 10.4169/math.mag.85.1.51.
  5. Brothers, H. J. (2012), "Pascal's triangle: The hidden stor-e", The Mathematical Gazette 96: 145–148.
  6. Fine, N. J. (1947), "Binomial coefficients modulo a prime", American Mathematical Monthly 54: 589–592, DOI 10.2307/2304500. See in particular Theorem 2, which gives a generalization of this fact for all prime moduli.
  7. Hasonló példa itt: Hore, P. J. (1983), "Solvent suppression in Fourier transform nuclear magnetic resonance", Journal of Magnetic Resonance 55 (2): 283–300, DOI 10.1016/0022-2364(83)90240-8.
  8. Karl, John H. (2012), An Introduction to Digital Signal Processing, Elsevier, p. 110, ISBN 9780323139595, <http://books.google.com/books?id=9Dv1PClLZWIC&pg=PA110>.
  9. Wolfram, S.. A New Kind of Science. Champaign IL: Wolfram Media, 870, 931–2. o (2002) 

Fordítás[szerkesztés | forrásszöveg szerkesztése]

Ez a szócikk részben vagy egészben a Pascal's triangle című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel.

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]

Magyar[szerkesztés | forrásszöveg szerkesztése]

Angol[szerkesztés | forrásszöveg szerkesztése]