Pascal-háromszög

$\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.

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)ⁿ 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.

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

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

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

(x + y)² = x² + 2xy + y² = 1x²y⁰ + 2x¹y¹ + 1x⁰y².

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)ⁿ = a₀xⁿ + a₁x^n‒1y + a₂x^n‒2y² + … + a_n‒1xy^n‒1 + a_nyⁿ,

ahol a kifejtés a_i 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 yⁿ együtthatójának, a következő átló az xy^n-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)ⁿ⁺¹ kifejtésének az együtthatóit az (x + 1)ⁿ 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 a₀ = a_n = 1)

Így most megkaptuk az (x + 1)ⁿ⁺¹ polinom kifejtését az (x + 1)ⁿ együtthatóinak függvényében (ezek az a_i-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)ⁿ polinom együtthatói
• és az (x + 1)ⁿ⁺¹ együtthatóit kell meghatároznunk.

Így minden i esetében, amely nem 0 és nem n + 1, az xⁱ tag együtthatója az (x + 1)ⁿ⁺¹ polinomban egyenlő a_i-(ez a meghatározandó számhoz képest balra fent van) + a_i‒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

Az átlók

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 tri_d függvény mértani értelmezése: minden d esetén tri_d(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 tri_d(1) = 1-nek felel meg. Ezeket az új pontokat a Pascal-háromszöghöz hasonló módon helyezzük el. A tri_d(x) értékenek meghatározásához: x pont alkotja a sokszöget. tri_d(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 tri₁(x) = x, amely a természetes számok sorozata. A pontok száma mindegyik rétegben tri_d ‒ 1(x) -nak felel meg.

Sierpinski-háromszög

Egyéb mintázatok és tulajdonságok

• 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 11ⁿ lesz az érték. Például a kettes sor az '1, 2, 1' számokkal (121) éppen a 11² -et adja. Az ötödik sorban '1, 5, 10, 10, 5, 1' az átvitel után 161051 lesz, ami 11⁵. 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

• 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

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

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

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

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 2^m‒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

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

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

• Binomiális együttható
• Binomiális együtthatók listája

Külső hivatkozások

Magyar

• A Pascal-háromszög szimmetriája, Kempelen Farkas Digitális Tankönyvtár
• A Pascal-háromszög néhány más tulajdonsága, Kempelen Farkas Digitális Tankönyvtár

Angol

• Weisstein, Eric W.: Pascal's triangle. MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/PascalsTriangle.html (angolul)
• The Old Method Chart of the Seven Multiplying Squares (from the Ssu Yuan Yü Chien of Chu Shi-Chieh, 1303, depicting the first nine rows of Pascal's triangle)
• Pascal's Treatise on the Arithmetic Triangle (page images of Pascal's treatise, 1655; summary: [2])
• Earliest Known Uses of Some of the Words of Mathematics (P)
• Leibniz and Pascal triangles
• Dot Patterns, Pascal's Triangle, and Lucas' Theorem
• Pascal's Triangle From Top to Bottom
• Omar Khayyam the mathematician
• Info on Pascal's Triangle
• Explanation of Pascal's Triangle and common occurrences, including link to interactive version specifying # of rows to view