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

Tartalomjegyzék

1 A háromszög
2 A Pascal-háromszög és a binomiális kifejtés
3 Tulajdonságok
4 Táblázat a fenti OEIS példához hasonlóan
5 A fenti táblázat binomiális együtthatókkal
6 A táblázat soraiban levő számok értelmezése
7 Még kifinomultabb minták
- 7.1 Hatványmátrix
8 Történet
9 Hivatkozások
10 Külső hivatkozások
- 10.1 Magyar
- 10.2 Angol

[szerkesztés] 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

[szerkesztés] 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ⁿ⁻¹y + a₂xⁿ⁻²y² + … + a_n−1xyⁿ⁻¹ + 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.

[szerkesztés] Tulajdonságok

[szerkesztés] 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 jobboldali á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

[szerkesztés] 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.

[szerkesztés] 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://www.research.att.com/~njas/sequences/A129352

[szerkesztés] 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

[szerkesztés] 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

[szerkesztés] 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

[szerkesztés] 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 $(2 m - 1)$ -edik sor középső tagjával. Például $12 + 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 $24 = 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.

[szerkesztés] Hatványmátrix

Bővebben: Pascal-mátrix

Mivel faktoriálisokból épül fel, a Pascal-háromszög felírható hatványmátrixké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

[szerkesztés] 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.

[szerkesztés] Hivatkozások

^ [1]
^ Pascal’s Triangle by Andrew Samuels
^ Nagativ vagy n-nél nagyobb k esetében a binomiális együttható értékét nullának tekintjük.

[szerkesztés] Külső hivatkozások

[szerkesztés] 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

[szerkesztés] Angol

Eric W. Weisstein, Pascal's triangle (MathWorld).
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

Kategória: Kombinatorika

See also ebooksgratis.com: no banners, no cookies, totally FREE.