Binomiális együttható

Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye.

Ez a szócikk vagy szakasz lektorálásra, tartalmi javításokra szorul. A felmerült kifogásokat a szócikk vitalapja részletezi (vagy extrém esetben a szócikk szövegében elhelyezett, kikommentelt szövegrészek). Ha nincs indoklás a vitalapon (vagy szerkesztési módban a szövegközben), bátran távolítsd el a sablont! Csak akkor tedd a lap tetejére ezt a sablont, ha az egész cikk megszövegezése hibás. Ha nem, az adott szakaszba tedd, így segítve a lektorok munkáját!

A matematikában az ${\displaystyle {\tbinom {n}{k}}}$ binomiális együttható a binomiális tételben előforduló együttható, ami a matematika különböző ágaiban bír jelentőséggel. Az ${\displaystyle {\tbinom {n}{k}}}$ kifejezést a magyarban így olvassák: „n alatt a k”.

Algebrai megközítésben ${\displaystyle {\tbinom {n}{k}}}$ az ${\displaystyle (1+x)^{n}}$ kifejtésében az ${\displaystyle x^{k}}$ együtthatója. A kombinatorikában ${\displaystyle {\tbinom {n}{k}}}$ egy n elemű halmaz k elemű részhalmazainak a száma, ami azt mutatja meg, hányféleképpen választható ki k elem n különböző elem közül.

Az ${\displaystyle {\tbinom {n}{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 ${\displaystyle ^{n}C_{k}}$, ${\displaystyle C_{k}^{n}}$, ${\displaystyle C_{n}^{k}}$, melyek mindegyikében a C betű a kombinációkra utal.

Definíció

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

${\displaystyle (x+y)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{n-k}y^{k}}$,

ami megmagyarázza a „binomiális együttható” nevet.

A binomiális együttható jelöli a kombinatorikában azt a számot, ahányféleképpen ki tudunk választani n különböző elemből k darabot, feltéve, hogy a kiválasztás sorrendje nem számít és minden elem legfeljebb egyszer választható (n elem k-adosztályú ismétlés nélküli kombinációinak száma); ezzel ekvivalens, hogy egy n-elemű halmazban a k-elemű részhalmazok (vagy k-kombinációk) számát is a binomiális együttható adja meg.

Rekurzív képlet

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

${\displaystyle {\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:

${\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1\quad {\mbox{minden n-nél, ahol }}n\in \mathbb {N} ,}$

${\displaystyle {\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 ${\displaystyle {\tbinom {n}{k}}=0}$ amikor k > n, és ${\displaystyle {\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:

${\displaystyle {\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:

${\displaystyle {\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)!-sal 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)

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

Tulajdonságai

A binomiális együtthatók összege

${\displaystyle \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 ${\displaystyle x=y=1}$ helyettesítéssel.

Alternáló összeg

${\displaystyle \sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}={\binom {n}{0}}-{\binom {n}{1}}+{\binom {n}{2}}-\dotsb =0}$ minden ${\displaystyle 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 ${\displaystyle x=1}$ és ${\displaystyle y=-1}$ (vagy ${\displaystyle x=-1}$ és ${\displaystyle y=1}$) helyettesítéssel.

Eltolt összeg

${\displaystyle \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

${\displaystyle \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 ${\displaystyle (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 ${\displaystyle {\tbinom {n}{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 ${\displaystyle n\in \mathbb {N} _{0}}$, ${\displaystyle z\in \mathbb {C} \setminus \{1\}}$ és ${\displaystyle |z|\geq 1}$ akkor

${\displaystyle \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 ${\displaystyle |z|\leq 1}$, ${\displaystyle z\neq -1}$ és ${\displaystyle \alpha \in \mathbb {C} }$, akkor a

${\displaystyle \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 ${\displaystyle m,n\geq 0}$-re, hogy

${\displaystyle \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

${\displaystyle \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 ${\displaystyle z,s\in \mathbb {C} }$, ${\displaystyle -z,-s\notin \mathbb {N} }$ és ${\displaystyle s+z\neq -1}$

${\displaystyle \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 ${\displaystyle -z\notin \{0,1,2,\dots ,n\}}$-re:

${\displaystyle \sum \limits _{k=0}^{n}{\binom {n}{k}}{\frac {(-1)^{k}}{z+k}}={\frac {n!}{z\,(z+1)\,(z+2)\cdot ...\cdot (z+n)}}}$.

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

${\displaystyle {\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

${\displaystyle \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

${\displaystyle \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 ${\displaystyle n\to \infty }$ határátmenet éppen a Gauss-féle

${\displaystyle \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

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

${\displaystyle \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 ${\displaystyle m}$szerinti indukcióval belátható. Az ${\displaystyle n=m}$ speciális esetre az egyenlet

${\displaystyle \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

${\displaystyle \sum \limits _{k=1}^{\infty }{\binom {x}{k}}{\frac {(-1)^{k-1}}{k}}=\psi (x+1)+\gamma }$

ahol ${\displaystyle \gamma }$ Euler-Mascheroni-konstans és ${\displaystyle \psi (x)}$a digammafüggvény, interpolálja a ${\displaystyle 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:

${\displaystyle {\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:

${\displaystyle {\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

Jegyzetek

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.

Forrá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.