Binomiális együttható

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, 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 $^{n}C_{k}$, $C_{k}^{n}$, $C_{n}^{k}$, melyek mindegyikében a C kombinációkat, választási lehetőségeket jelöl.

Definíció

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 {n}{k}}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)ⁿ 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 X^k-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 {n}{k}}$ 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

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

${\binom {n}{k}}={\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 {n}{0}}={\binom {n}{n}}=1\quad {\mbox{minden n-nél, ahol }}n\in \mathbb {N} ,$

${\binom {0}{k}}=0\quad {\mbox{minden egésznél, ahol }}k>0.$

A képlet vagy megszámolja a kitevőket X^k-ig (1 + X)ⁿ⁻¹(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 {n}{k}}=0$ amikor k > n, és ${\tbinom {n}{n}}=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

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 {n}{k}}={\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ámláló 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

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

${\binom {n}{k}}={\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ő (n − k)!-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 {n}{k}}={\binom {n}{n-k}}\quad {\mbox{ahol }}\ 0\leq k\leq n.$

Tulajdonságai

A binomiális együtthatók összege

$\sum _{k=0}^{n}{\binom {n}{k}}={\binom {n}{0}}+{\binom {n}{1}}+\dotsb +{\binom {n}{n}}=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

$\sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}={\binom {n}{0}}-{\binom {n}{1}}+{\binom {n}{2}}-\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

$\sum _{k=0}^{m}{\binom {n+k}{n}}={\binom {n}{n}}+{\binom {n+1}{n}}+\dotsb +{\binom {n+m}{n}}={\binom {n+m+1}{n+1}}$

Vandermonde-azonosság

$\sum _{j=0}^{k}{\binom {m}{j}}{\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

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

A kombinatorikában

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

Binomiális sorok

Ha $n\in \mathbb {N} _{0}$, $z\in \mathbb {C} \setminus \{1\}$ és $|z|\geq 1$ akkor

$\sum _{k=0}^{\infty }{\binom {k}{n}}{\frac {1}{z^{k+1}}}=\sum _{k=n}^{\infty }{\binom {k}{n}}{\frac {1}{z^{k+1}}}={\frac {1}{(z-1)^{n+1}}}$,

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

Hogyha $|z|\leq 1$, $z\neq -1$ és $\alpha \in \mathbb {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

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

$\sum \limits _{k=0}^{n}{\binom {n}{k}}{\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 {n}{k}}{\frac {(-1)^{k}}{m+k+1}}=\sum \limits _{k=0}^{m}{\binom {m}{k}}{\frac {(-1)^{k}}{n+k+1}}$

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

$\sum \limits _{k=0}^{\infty }{\binom {s}{k}}{\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

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

$\sum \limits _{k=0}^{n}{\binom {n}{k}}{\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

${\frac {1}{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 {n}{k}}{\frac {(-1)^{k}}{z+k}}=\int \limits _{0}^{1}t^{z-1}(1-t)^{n}\mathrm {d} t=n^{-z}\int \limits _{0}^{n}t^{z-1}\left(1-{\frac {t}{n}}\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}^{n}t^{z-1}\left(1-{\frac {t}{n}}\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.

A digamma és az Euler-Mascheroni konstans

Minde $m,n\in \mathbb {N}$-re, amire $m\leq n$

$\sum \limits _{k=1}^{m}{\binom {n}{m-k}}{\frac {(-1)^{k-1}}{k}}={\binom {n}{m}}\sum \limits _{k=n-m+1}^{n}{\frac {1}{k}}$,

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

$\sum \limits _{k=1}^{n}{\binom {n}{k}}{\frac {(-1)^{k-1}}{k}}=\sum \limits _{k=1}^{n}{\frac {1}{k}}$.

Az összeget a sorral helyettesítve

$\sum \limits _{k=1}^{\infty }{\binom {x}{k}}{\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}{\frac {1}{k}}$ sorozatot.

Általánosításai

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 {a}{k}}={\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 (x₁+x₂+ … + x_m)ⁿ 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 k_i nemnegatív, és összegük egyenlő n-nel.

Kapcsolódó szócikkek

• Pascal-háromszög
• Binomiális együtthatók listája

Hivatkozások

• Fowler, David (1996. January). „The Binomial Coefficient Function”. The American Mathematical Monthly 103 (1), 1–17. o, Kiadó: Mathematical Association of America. DOI:10.2307/2975209.  

Fordítá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. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.