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
a k-adik binomiális együttható az (x+y)n kifejtésében, akkor
bármely nem negatív egész n és bármely 0 és n közötti egész k esetében.Negativ vagy n-nél nagyobb k esetében a binomiális együttható értékét nullának tekintjük.
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)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
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
Akkor
A két összeget a következőképpen lehet átrendezni:
(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 , és így
Más szóval, a Pascal-háromszög n-edik sorában a tagok összege 2 n-edik hatványa.
Kombinációk 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
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 A sorok 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...
Tehát a sorozat így definiálható:
Az egymást követő tagok hányadosa:
aminek hányadosa:
A fenti egyenlet jobb oldaláról tudjuk, hogy az e-hez tart:
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 átvíve 11 további, nagyobb kitevőjű hatványai adódnak. Más alapú számrendszerekben is 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. 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) Hatos számrendszerben: 1 3 3 16 = 73 (343) ⟨1, 4, 6, 4, 1⟩ → 1 5 0 4 16 = 74 (2401) 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) Tízes számrendszerben: 1 2 110 = 112 (121) ⟨1, 5, 10, 10, 5, 1⟩ → 1 6 1 0 5 110 = 115 (161051) ⟨1, 6, 15, 20, 15, 6, 1⟩ → 1 7 7 1 5 6 110 = 116 (1771561) Tizenhatos számrendszerben: 1 5 10 10 5 116 = 175 (1419857) ⟨1, 6, 15, 20, 15, 6, 1⟩ → 1 7 0 4 15 6 116 = 176 (24137569) 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:
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 és osztója -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.. See in particular Theorem 2, which gives a generalization of this fact for all prime moduli. Polaritás: Az egy sorban álló számokat váltakozó előjellel összeadva nullát kapunk.
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 negyedik á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:
Más képlet:
Rekurzió nélkül:
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 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ő:
Például az ötödik sor:, , , és , így az elemek , , . A további elemek a szimmetria tulajdonság alapján az előbbiek tükörképei.
Az , , , ... elemeket tartalmazó átló kiszámítására újra -gyel kezdünk, és a további elemek a
törtekkel való szorzással kaphatók.
Például az -val kezdődő átlón a törtek: , , , ..., így az elemek , , . A további elemek a szimmetria tulajdonság miatt az előzőek tükörképei.
Egyéb mintázatok és tulajdonságok bélyegkép|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. thumb|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.
Egy további tulajdonság akkor válik nyilvánvalóvá, ha a háromszög sorait balra igazítjuk. Ekkor az (azonos színnel megjelölt) átlók mentén képezve az összegeket, a Fibonacci-számokat kapjuk. (Például, a kék átlóval kezdve, 1 + 3 + 1 = 5, 1 + 4 + 3 = 8, 1 + 5 + 6 + 1 = 13...)
{| style="align:center;" |- align=center |bgcolor=red|1 |- align=center | style="background:orange;"|1 | style="background:yellow;"|1 |- align=center | style="background:yellow;"|1 |bgcolor=lime|2 |bgcolor=aqua|1 |- align=center |bgcolor=lime|1 |bgcolor=aqua|3 | style="background:violet;"|3 |bgcolor=red|1 |- align=center |bgcolor=aqua|1 | style="background:violet;"|4 |bgcolor=red|6 | style="background:orange;"|4 | style="background:yellow;"|1 |- align=center | style="background:violet;"|1 |bgcolor=red|5 | style="background:orange;"|10 | style="background:yellow;"|10 |bgcolor=lime|5 |bgcolor=aqua|1 |- align=center |bgcolor=red|1 | style="background:orange;"|6 | style="background:yellow;"|15 |bgcolor=lime|20 |bgcolor=aqua|15 | style="background:violet;"|6 |bgcolor=red|1 |- align=center | style="background:orange;"|1 | style="background:yellow;"|7 |bgcolor=lime|21 |bgcolor=aqua|35 | style="background:violet;"|35 |bgcolor=red|21 | style="background:orange;"|7 | style="background:yellow;"|1 |- align=center | style="background:yellow; width:50px;"|1 | style="background:lime; width:50px;"|8 | style="background:aqua; width:50px;"|28 | style="background:violet; width:50px;"|56 | style="background:red; width:50px;"|70 | style="background:orange; width:50px;"|56 | style="background:yellow; width:50px;"|28 | style="background:lime; width:50px;"|8 | style="background:aqua; width:50px;"|1
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 9245 7 vagy AAAAABBBBBBB 7 105 350 350 105 7 9244 8 vagy AAAABBBBBBBB 28 224 420 224 28 9243 9 vagy AAABBBBBBBBB 84 378 378 84 9242 10 vagy AABBBBBBBBBB 210 504 210 9241 11 vagy ABBBBBBBBBBB 462 462 924 0 12 vagy BBBBBBBBBBBB 924 924