Binomiális együttható

A matematikában az $(\binom{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 $(\binom{n}{k})$ kifejezést a magyarban így olvassák: „n alatt a k”. Algebrai megközítésben $(\binom{n}{k})$ az $(1 + x)^{n}$ kifejtésében az $x^{k}$ együtthatója. A kombinatorikában $(\binom{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 $(\binom{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 $n C_{k}$ , $C_{k}^{n}$ , $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 $(\binom{n}{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 tételben.

(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.

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}) minden olyan egészre, ahol n, k > 0,

ezekkel a kezdőértékekkel:

(\binom{n}{0}) = (\binom{n}{n}) = 1 minden n-nél, ahol n \in ℕ,

(\binom{0}{k}) = 0 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 $(\binom{n}{k}) = 0$ amikor k > n, és $(\binom{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) \dots (n - k + 1)}{k (k - 1) (k - 2) \dots 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)!} 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)

(\binom{n}{k}) = (\binom{n}{n - k}) 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}) + \dots + (\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}) - \dots = 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}) + \dots + (\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 $(\binom{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 $n \in ℕ_{0}$ , $z \in ℂ ∖ {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 $α \in ℂ$ , akkor a

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

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

,

a szimmetria miatt

\sum_{k = 0}^{n} (\binom{n}{k}) \frac{(- 1)^{k}}{m + k + 1} = \sum_{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 ℂ$ , $- z, - s \notin ℕ$ és $s + z \neq - 1$

\sum_{k = 0}^{\infty} (\binom{s}{k}) \frac{(- 1)^{k}}{z + k + 1} = \frac{1}{(z + s + 1) (\binom{z + s}{s})} = B (z + 1, s + 1)

.

A gammafüggvény

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

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

.

$R e z > 0$ esetén a törtek felírhatók integrálokként

\frac{1}{z + k} = \int_{0}^{1} t^{z + k - 1} d t

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

\sum_{k = 0}^{n} (\binom{n}{k}) \frac{(- 1)^{k}}{z + k} = \int_{0}^{1} t^{z - 1} (1 - t)^{n} d t = n^{- z} \int_{0}^{n} t^{z - 1} {(1 - \frac{t}{n})}^{n} 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_{0}^{n} t^{z - 1} {(1 - \frac{t}{n})}^{n} 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

Γ (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 $m, n \in ℕ$ -re, amire $m \leq n$

\sum_{k = 1}^{m} (\binom{n}{m - k}) \frac{(- 1)^{k - 1}}{k} = (\binom{n}{m}) \sum_{k = n - m + 1}^{n} \frac{1}{k}

,

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

\sum_{k = 1}^{n} (\binom{n}{k}) \frac{(- 1)^{k - 1}}{k} = \sum_{k = 1}^{n} \frac{1}{k}

.

Az összeget a sorral helyettesítve

\sum_{k = 1}^{\infty} (\binom{x}{k}) \frac{(- 1)^{k - 1}}{k} = ψ (x + 1) + γ

ahol $γ$ Euler-Mascheroni-konstans és $ψ (x)$ a digammafüggvény, interpolálja a $a_{n} = \sum_{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) \dots (a - k + 1)}{k (k - 1) (k - 2) \dots 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

Jegyzetek

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

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.

[1] Nicholas J. Higham. Handbook of writing for the mathematical sciences. SIAM, 25. o. (1998). ISBN 0898714206

[2] Disquisitiones generales circa seriem infinitam 1+…, 1813, S. 26 (auch in Carl Friedrich Gauß: Werke. Band 3, S. 145)

[1]

[2]