Binomiális együttható

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

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

A kombinatorikában _{n \choose k} 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 _{n \choose k} 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 ^nC_k, C^n_k, C^k_n, melyek mindegyikében a C kombinációkat, választási lehetőségeket jelöl.

Definíció[szerkesztés | forrásszöveg szerkesztése]

Az n és k természetes számoknál, az _{n \choose k} binomiális együtthatót az egytagú X^k együtthatójaként lehet leírni az (1+X)^n kifejezésben. Ugyanez az együttható fordul elő, ha k ≤ n a binomiális képletben.

(x+y)^n=\sum_{k=0}^n\binom nk x^{n-k}y^k

(é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 \tbinom nk 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 | forrásszöveg szerkesztése]

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

 \binom nk = \binom{n-1}{k-1} + \binom{n-1}k \quad \mbox{minden olyan egészre, ahol }n,k>0,

ezekkel a kezdőértékekkel:

\binom n0 = \binom nn = 1 \quad \mbox{minden n-nél, ahol } n \in \N,
\binom 0k = 0 \quad \mbox{minden egésznél, ahol } k>0.

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 \tbinom nk=0 amikor k > n, és \tbinom nn=1 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 | forrásszöveg szerkesztése]

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

\binom nk = \frac{n^{\underline k}}{k!} = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k(k-1)(k-2)\cdots 1}=\prod_{i=1}^k \frac{n-k+i}{i}.

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 | forrásszöveg szerkesztése]

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

 \binom nk = \frac{n!}{k!\,(n-k)!} \quad \mbox{ahol }\ 0\leq k\leq n.

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)

 \binom nk = \binom n{n-k} \quad \mbox{ahol }\ 0\leq k\leq n.

Tulajdonságai[szerkesztés | forrásszöveg szerkesztése]

A binomiális együtthatók összege[szerkesztés | forrásszöveg szerkesztése]

\sum_{k=0}^n \binom nk = \binom n0 + \binom n1 + \dotsb + \binom nn = 2^n.

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 x = y = 1 helyettesítéssel.

Alternáló összeg[szerkesztés | forrásszöveg szerkesztése]

\sum_{k=0}^n (-1)^k \binom nk = \binom n0 - \binom n1 + \binom n2 - \dotsb = 0 minden n>0.

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 x = 1 és y = -1 (vagy x = -1 és y = 1) helyettesítéssel.

Eltolt összeg[szerkesztés | forrásszöveg szerkesztése]

\sum_{k=0}^m \binom{n+k}n = \binom nn + \binom{n+1}n + \dotsb + \binom{n+m}n = \binom{n+m+1}{n+1}

Vandermonde-azonosság[szerkesztés | forrásszöveg szerkesztése]

\sum_{j=0}^k \binom mj \binom n{k-j} = \binom{m+n}k.

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 (1+x)^{m+n}=(1+x)^m(1+x)^n felbontásból és az együtthatók összehasonlításából adódik.

Alkalmazásai[szerkesztés | forrásszöveg szerkesztése]

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

A kombinatorikában[szerkesztés | forrásszöveg szerkesztése]

A binomiális együtthatók központi szerephez jutnak a leszámláló kombinatorikában, ahol is _{n \choose k} 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 | forrásszöveg szerkesztése]

Binomiális sorok[szerkesztés | forrásszöveg szerkesztése]

Ha n\in\mathbb{N}_0, z\in\mathbb{C}\setminus\{1\} és |z|\ge 1 akkor

\sum_{k=0}^\infty\binom kn\frac1{z^{k+1}}=\sum_{k=n}^\infty\binom kn\frac1{z^{k+1}}=\frac{1}{(z-1)^{n+1}},

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

Hogyha |z|\le 1, z\ne-1 és \alpha\in\C, akkor a

\sum_{k=0}^\infty\binom\alpha k z^k=(1+z)^\alpha

binomiális sor szintén konvergál.

A bétafüggvény[szerkesztés | forrásszöveg szerkesztése]

Teljes indukcióval bizonyítható minden m,n\ge 0-re, hogy

\sum\limits_{k=0}^n\binom nk\frac{(-1)^k}{m+k+1}=\dfrac{1}{(m+n+1)\displaystyle\binom{m+n}m},

a szimmetria miatt

\sum\limits_{k=0}^n\binom nk\frac{(-1)^k}{m+k+1}=\sum\limits_{k=0}^m\binom mk\frac{(-1)^k}{n+k+1}

A bétafüggvény kiterjeszthető a komplex számok halmazára, ha z,s\in\C, -z,-s\notin\N és s+z\ne-1

\sum\limits_{k=0}^\infty\binom sk\frac{(-1)^k}{z+k+1}=\dfrac{1}{(z+s+1)\displaystyle\binom{z+s}s}=\mathrm{B}(z+1,s+1).

A gammafüggvény[szerkesztés | forrásszöveg szerkesztése]

Minden -z\notin\{0,1,2,\dots,n\}-re:

\sum\limits_{k=0}^n\binom nk\frac{(-1)^k}{z+k}=\frac{n!}{z\,(z+1)\,(z+2)\cdot...\cdot(z+n)}.

\mathrm{Re}\,z>0 esetén a törtek felírhatók integrálokként

\frac1{z+k}=\int\limits_0^1 t^{z+k-1}\mathrm{d}t

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

\sum\limits_{k=0}^n\binom nk\frac{(-1)^k}{z+k}=
\int\limits_0^1t^{z-1}(1-t)^n\mathrm{d}t=
n^{-z}\int\limits_0^nt^{z-1}\left(1-\frac tn\right)^n\mathrm{d}t
,

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

\int\limits_0^nt^{z-1}\left(1-\frac tn\right)^n\mathrm{d}t=\frac{n^z\,n!}{z\,(z+1)\,(z+2)\cdot...\cdot(z+n)}

alakot nyeri, ahol a n\to\infty határátmenet éppen a Gauss-féle

\Gamma(z)=\lim\limits_{n\to\infty}\frac{n^z\,n!}{z\,(z+1)\,(z+2)\cdot...\cdot(z+n)},

alakot adja.[2]

A digamma és az Euler-Mascheroni konstans[szerkesztés | forrásszöveg szerkesztése]

Minde m,n\in\N-re, amire m\le n

\sum\limits_{k=1}^m\binom n{m-k}\frac{(-1)^{k-1}}k=\binom nm\sum\limits_{k=n-m+1}^n\frac1k,

ami mszerinti indukcióval belátható. Az n=m speciális esetre az egyenlet

\sum\limits_{k=1}^n\binom nk\frac{(-1)^{k-1}}k=\sum\limits_{k=1}^n\frac1k.

Az összeget a sorral helyettesítve

\sum\limits_{k=1}^\infty\binom xk\frac{(-1)^{k-1}}k=\psi(x+1)+\gamma

ahol \gamma Euler-Mascheroni-konstans és \psi(x)a digammafüggvény, interpolálja a a_n=\sum\limits_{k=1}^n\frac1k sorozatot.

Általánosításai[szerkesztés | forrásszöveg szerkesztése]

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:

\binom ak = \frac{a^{\underline k}}{k!} = \frac{a(a-1)(a-2)\cdots(a-k+1)}{k(k-1)(k-2)\cdots 1}=\prod_{i=1}^k \frac{a-k+i}{i}.

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:

 \binom n{k_1,k_2,\dots,k_m} = \frac{n!}{k_1!\,k_2!\,\dots \, k_m!}

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

Kapcsolódó szócikkek[szerkesztés | forrásszöveg szerkesztése]

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

  1. Nicholas J. Higham. Handbook of writing for the mathematical sciences. SIAM. 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 | forrásszöveg szerkesztése]

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.