A Pascal háromszög
A leírást ajánlom mindazoknak akik kicsit többet akarnak foglalkozni a kombinatórikával (gondolva itt IS tippre) vagy csak kíváncsiak, hogy mi ben segíthet a matematika.
A végtelenül folytatható számtáblázatról és annak kombinatorikai jelentőségéről először Blaise Pascal jelentetett meg írást. Manapság szokásosabb így elrendezni a háromszöget:
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
Ezt a háromszöget Pascal háromszögnek nevezzük.
Az egy darab egyesből álló felső sor a Pascal háromszög 0. (nulladik) sora, utána lejjebb szokásosan jön az 1., 2., stb sor. A Pascal háromszög n-edik sorában tehát n+1 szám van, a szélsők 1-esek mellettük egy-egy n áll (ha n>0).
Az egyes sorokon belül is 0-tól sorszámozzuk az elemeket, tehát pld a vastagított 56-os szám a Pascal háromszög 8. sorának 3. eleme.
A Pascal háromszög rekurzív előállítása:
A felső sorba – a háromszög csúcsába - írjunk egy 1-est és minden további elem legyen a fölötte (balra fölötte és jobbra fölötte) lévő egy vagy két elem összege.
A Pascal háromszög közvetlen kombinatorikai jelentése:
Az adott helyre írt szám megmondja, hogy hányféleképpen juthatunk el a háromszög csúcsából az adott helyre, ha csak balra lefelé és jobbra lefelé léphetünk.
A Pascal háromszög explicit előállítása:
A 8.sor 3. eleme az 56, ezt a formula is megadja. Általában, az n-edik sor k-adik elemét megadó képlet: (A tört számlálójában k tényező van.) Ez a kifejezés (n – k) faktoriálissal bővítve így is írható: