Binomiális együttható

A Wikipédiából, a szabad enciklopédiából

A matematikában, az binomiális együttható az (1 + x) n-edik hatványának többtagú kifejezésében az együtthatója. Az kifejezést a magyarban így olvassák: "n alatt a k".

A kombinatorikában egy n elemű halmaz k elemű részhalmazainak a száma, ami azt mutatja meg, hányféleképpen "választhatunk ki" k elemet n elem közül. Az jelölést Andreas von Ettingshausen vezette be 1826-ban,[1] habár a számokat már századokkal előtte is ismerték (lásd Pascal-háromszög). Alternatív jelölések a , , , melyek mindegyikében a C kombinációkat, választási lehetőségeket jelöl.

Definíció[szerkesztés]

Az n és k természetes számoknál, az binomiális együtthatót az egytagú együtthatójaként lehet leírni az kifejezésben. Ugyanez az együttható fordul elő, ha k ≤ n a binomiális képletben.

(érvényes egy kommutatív gyűrű akármelyik x, y elemeire), ami megmagyarázza a "binomiális együttható" nevet.

Ez a szám a kombinatorikában is előfordul, ahol (a sorba rendezést elhanyagolva), a k tárgyak n tárgyakból való kiválasztását mutatja; azaz a k elemű részhalmazok (vagy k-kombinációk egy n elemű halmazban. Ez a szám egyenlőnek tekinthető az első definícióban írt számmal, függetlenül akármelyik lenti kiszámítási képlettől: ha a kifejezés mindegyik n faktorja (1 + X)n ideiglenesen megjelöli az X kifejezést egy i indexszel (1-től n-ig), akkor a k jelzőszám mindegyik részhalmaza a kifejezés után egy Xk-t tesz, és annak az egytagú kifejezésnek az eredménye lesz az ilyen részhalmazok száma. Ez azt mutatja meg, hogy az n és k természetes számoknál természetes szám lesz. Sok kombinatorikai értelmezése van a binomiális együtthatóknak (számolási feladatok, amiknél egy binomiális együtthatós kifejezés adja a választ) például az n bitek (0 vagy 1) által kialakított szavak, amiknek összege k, de a legtöbbjük azonos értékű, mint a k-kombinációk száma.

Rekurzív képlet[szerkesztés]

Van egy rekurzív képlete a binomiális együtthatóknak.

ezekkel a kezdőértékekkel:

A képlet vagy megszámolja a kitevőket Xk-ig (1 + X)n−1(1 + X)-ben, vagy a {1, 2, ..., n} k'-kombinációit számolja meg, külön-külön azt, ami tartalmazza az n-et és ami nem. Ebből adódik, hogy amikor k > n, és minden n-re, hogy az ilyen eseteknél a rekurzió megállhasson. Ez a rekurzív képlet lehetővé teszi a Pascal-háromszög szerkesztését.

Szorzási képlet[szerkesztés]

Egy, egyedi binomiális együtthatók kiszámítására alkalmazott, hatékonyabb módot ez a képlet jeleníti meg:

Ezt a képletet legkönnyebb megérteni a binomiális együttható kombinatorikai értelmezéséhez. A számlaló megadja a k eltérő tárgyak számsorának n tárgyak halmazából való kiválasztásához szükséges eljárások számát, megőrizve a kiválasztás sorrendjét. A nevező megszámolja az eltérő számsorok számát, amik ugyanazt a k-kombinációt határozzák meg, amikor nem vesszük figyelembe a sorrendet.

Faktoriális képlet[szerkesztés]

Végül, van egy faktoriálisokat használó könnyen megjegyezhető képlet:

ahol n! az n faktoriálisát fejezi ki. Ez a képlet a fenti szorzási képletből adódik a számláló és nevező (nk)!-vel való megszorzásával; következményképpen a számláló és nevező sok közös tényezőjét magában foglalva. Kevésbé praktikus nyílt számításra, hacsak nem iktatjuk ki a közös tényezőket először (mivel a faktoriális értékek nagyon gyorsan nőnek). A képlet egy szimmetriát is mutat, ami nem annyira nyilvánvaló a szorzási képletből (habár a definíciókból jön)

Tulajdonságai[szerkesztés]

A binomiális együtthatók összege[szerkesztés]

Ez éppen egy n elemű halmaz részhalmazait számolja le elemszám szerint. Az összegzési képlet levezethető a binomiális tételből az helyettesítéssel.

Alternáló összeg[szerkesztés]

minden .

Kombinatorikai jelentése: egy halmaznak ugyanannyi páros, mint páratlan elemszámú részhalmaza van. A képlet páratlan n-re azonnal következik a szimmetriából. Tetszőleges n-re belátható a binomiális tétellel és az és (vagy és ) helyettesítéssel.

Eltolt összeg[szerkesztés]

Vandermonde-azonosság[szerkesztés]

Az állítás kombinatorikai érveléssel belátható:

Vegyük gömbök n+m elemű halmazát, amiben m gömb piros. Leszámláljuk a gömbök k elemű részhalmazait aszerint, hogy mennyi piros gömböt tartalmaznak.

Egy másik bizonyítás az felbontásból és az együtthatók összehasonlításából adódik.

Alkalmazásai[szerkesztés]

A binomiális együtthatóknak több különféle alkalmazása van.

A kombinatorikában[szerkesztés]

A binomiális együtthatók központi szerephez jutnak a leszámláló kombinatorikában, ahol is az n elemű halmaz k elemű részhalmazainak száma, vagyis ennyiféleképpen lehet n elem közül kiválasztani k-t a sorrend figyelembe vétele nélkül.

Szemléletesen, kiszámítjuk az összes n hosszú sorozatot, majd kiválasztunk k helyet, és azt akarjuk tudni, hogy hányféleképpen tölthetők fel ezek a helyek. Mivel az elemek sorrendje nem játszik szerepet, ezért osztani kell k!-sal; és mivel az érdektelen elemek sorrendje szintén nem fontos, ezért osztunk (n-k)!-sal is.

Az analízisben[szerkesztés]

Binomiális sorok[szerkesztés]

Ha , és akkor

,

amely binomiális sor a mértani sorok általánosítása.

Hogyha , és , akkor a

binomiális sor szintén konvergál.

A bétafüggvény[szerkesztés]

Teljes indukcióval bizonyítható minden -re, hogy

,

a szimmetria miatt

A bétafüggvény kiterjeszthető a komplex számok halmazára, ha , és

.

A gammafüggvény[szerkesztés]

Minden -re:

.

esetén a törtek felírhatók integrálokként

a hatványokat a binomiális képlet szerint összegezve

,

ahol az utolsó integrálban t-t helyettesítünk t/n-be. Be kell még látni, hogy a helyettesítések elvégezhetők, és a főbb tulajdonságok megmaradnak. Így az egyenlőtlenség a

alakot nyeri, ahol a határátmenet éppen a Gauss-féle

,

alakot adja.[2]

A digamma és az Euler-Mascheroni konstans[szerkesztés]

Minde -re, amire

,

ami szerinti indukcióval belátható. Az speciális esetre az egyenlet

.

Az összeget a sorral helyettesítve

ahol Euler-Mascheroni-konstans és a digammafüggvény, interpolálja a sorozatot.

Általánosításai[szerkesztés]

A binomiális együtthatónak több általánosítása is létezik.

A szorzási képlet alapján általánosítható valós a-kra és egész k-kra:

Minden a-ra és k=0-ra az értéke 1, és minden a-ra és negatív k-kra az értéke 0.

A multinomiális együtthatók az (x1+x2+ … + xm)n alakú polinomok együtthatói. A faktoriális képlet általánosításával számíthatók:

ahol minden ki nemnegatív, és összegük egyenlő n-nel.

Kapcsolódó szócikkek[szerkesztés]

Hivatkozások[szerkesztés]

  1. Nicholas J. Higham. Handbook of writing for the mathematical sciences. SIAM, 25. o. ISBN 0898714206 
  2. Disquisitiones generales circa seriem infinitam 1+…, 1813, S. 26 (auch in Carl Friedrich Gauß: Werke. Band 3, S. 145)

Fordítás[szerkesztés]

Ez a szócikk részben vagy egészben a Binomialkoeffizient című német Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel.