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 and 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.

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

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{and}\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}

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ékenek 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.

Sierpinski-háromszög

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

  • Az a minta, amelyet akkor kapunk, ha a Pascal-háromszögben a páratlan számokat kiszínezzük, a Sierpinski-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 Sierpinski-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.
  • 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.
  • Ha a sorokat úgy tekintjük, mintha tízes számrendszerben leírt számok lennének (és a 9-nél nagyobb számokat az összeadás szabályai szerint „átvisszük”), akkor ezek 11 hatványai lesznek, pontosabban az n-es sorban 11n lesz az érték. Például a kettes sor az '1, 2, 1' számokkal (121) éppen a 112 -et adja. Az ötödik sorban '1, 5, 10, 10, 5, 1' az átvitel után 161051 lesz, ami 115. Ez a tulajdonság könnyen megmagyarázható, ha az (x + 1)sor száma binomiális kifejtésében x = 10-et veszünk.

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 Yang Hui-háromszög kínai ábrázolása

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

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.

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]