A binomiális együttható bizonyítása: n alatt k kiválasztása
Ezt a munkát a tanárunk ellenőrizte: 5.08.2026 time_at 12:57
Feladat típusa: Analízis
Hozzáadva: 3.08.2026 time_at 14:18
Összefoglaló:
Bizonyítsd be a binomiális együttható képletét, és értsd meg, miért \(\binom{n}{k}=\frac{n!}{k!(n-k)!}\) az n elem k kiválasztásának száma.
Miért igaz, hogy \(\dfrac{n!}{k!(n-k)!}\) az \(n\) elem \(k\)-ad osztályú kombinációinak száma?
A kombinatorika az iskolai matematika egyik olyan területe, amely első pillantásra egyszerű felsorolásnak tűnhet, valójában azonban nagyon mély logikai gondolkodást kíván. Már az általános iskola felső tagozatától, majd különösen gimnáziumban is gyakran találkozunk olyan feladatokkal, hogy „hányféleképpen választhatunk ki” bizonyos számú elemet egy nagyobb halmazból. Ilyen helyzet lehet például, amikor egy osztályból versenyzőket kell kijelölni, egy diákkörből bizottságot alakítunk, vagy éppen egy lottószerű feladatban számoljuk a lehetőségeket. Ezekben a kérdésekben közös, hogy nem mindig mindegy, számít-e a sorrend vagy sem.Az \(n\) elem közül kiválasztott \(k\) elemű részhalmazok számát a matematika a binomiális együtthatóval jelöli:
\[ \binom{n}{k}=\frac{n!}{k!(n-k)!} \]
Ez az összefüggés sok diák számára először inkább képletként jelenik meg, mint valóban megértett állításként. Pedig a formula mögött nagyon világos gondolat rejlik. Nem „bemagolandó szabályról” van szó, hanem egy logikusan felépíthető számolási elvről. Ennek a dolgozatnak az a célja, hogy bebizonyítsa: az \(n\) különböző elem \(k\)-ad osztályú kombinációinak száma valóban \(\dfrac{n!}{k!(n-k)!}\). A bizonyítást nemcsak algebrai átalakításokkal, hanem a kombináció és a variáció kapcsolatának feltárásával is megadom, mert így érthetővé válik, miért éppen ez a képlet a helyes.
Alapfogalmak: mit számolunk valójában?
Mielőtt a bizonyítást felépítenénk, szükséges pontosan tisztázni, hogy miről beszélünk. A kombinatorikában egy-egy szó jelentése döntő fontosságú. Sok hiba onnan ered, hogy valaki összekeveri a „kiválasztást” a „rendezéssel”, vagy nem veszi észre, hogy ugyanazt az esetet többször számolta meg.Az \(n\) elem azt jelenti, hogy van egy olyan halmazunk, amely pontosan \(n\) darab, egymástól különböző elemet tartalmaz. Ezek az elemek lehetnek számok, személyek, tárgyak, betűk vagy bármilyen egyedileg megkülönböztethető dolgok. Ha például egy 32 fős osztályból kell kiválasztani 4 tanulót egy ünnepi műsorhoz, akkor itt \(n=32\), és a 32 tanuló mind külön személynek számít. A „különböző” kitétel nagyon lényeges. Ha az elemek között ismétlődés volna, egészen más típusú feladathoz jutnánk.
A \(k\)-ad osztályú kombináció azt jelenti, hogy az \(n\) elem közül kiválasztunk \(k\) darabot úgy, hogy a sorrend nem számít. Ha például egy háromfős zsűrit választunk ki az osztályból, akkor az a csoport, amelynek tagjai mondjuk Anna, Bence és Csilla, ugyanaz marad akkor is, ha a neveket más sorrendben írjuk le. A kombináció lényegében tehát részhalmazt jelent.
Ezzel szemben variációról akkor beszélünk, ha a kiválasztott elemek sorrendje is számít. Ha két tanulót választunk ki úgy, hogy egyikük lesz a csapatvezető, másikuk pedig a helyettes, akkor már nem ugyanaz az „Anna–Bence” és a „Bence–Anna” eset. Ilyenkor a sorrend szerepet kap, tehát nem kombinációt, hanem rendezett kiválasztást számolunk.
Ez a különbség lesz a bizonyítás kulcsa. A kombinációk számát ugyanis legegyszerűbben úgy kapjuk meg, hogy előbb megszámoljuk a rendezett eseteket, majd kijavítjuk azt a tényt, hogy ezzel minden sorrend nélküli választást többször is figyelembe vettünk.
A fő gondolat: előbb rendezetten számolunk
A bizonyítás legfontosabb ötlete az, hogy a sorrenddel történő kiválasztást könnyebb megszámolni, mint a sorrend nélkülit. Tegyük fel, hogy \(n\) különböző elemből szeretnénk \(k\) darabot kiválasztani úgy, hogy a kiválasztás sorrendje is számítson.Az első helyre az \(n\) elem közül bármelyiket tehetjük, tehát az első választásra \(n\) lehetőség van. Ha már kiválasztottunk egy elemet, akkor az a második helyre nem kerülhet újra, hiszen ugyanazt az elemet nem választjuk kétszer. Ezért a második helyre már csak \(n-1\) lehetőség marad. Hasonlóan, a harmadik helyre \(n-2\), a negyedikre \(n-3\), és így tovább. Amikor a \(k\)-adik helyhez érünk, addigra már \(k-1\) elemet kiválasztottunk, ezért a még rendelkezésre álló elemek száma \(n-k+1\).
A szorzási szabály alapján a rendezett kiválasztások száma tehát:
\[ n\cdot(n-1)\cdot(n-2)\cdots(n-k+1) \]
Ez a szorzat ismerős alakra hozható a faktoriális segítségével. Mivel
\[ n!=n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)\cdot(n-k)\cdots2\cdot1, \]
ezért ha \(n!\)-ból „levágjuk” az utolsó \((n-k)!\) tényezőt, akkor éppen a fenti szorzatot kapjuk. Vagyis a rendezett kiválasztások száma:
\[ \frac{n!}{(n-k)!} \]
Ez az úgynevezett ismétlés nélküli variációk száma. Már itt látszik, hogy a faktoriálisok nem valami önkényes díszítőelemek a képletben, hanem természetes módon jelennek meg abból, hogy egy csökkenő szorzatot akarunk tömörebben leírni.
Miért kell osztani \(k!\)-lal?
Most jön a bizonyítás második, igazán lényegi része. A \(\dfrac{n!}{(n-k)!}\) szám még nem a kombinációk száma, mert ebben a számolásban a sorrend is szerepet kapott. Nekünk viszont éppen az a kérdésünk, hányféleképpen választhatunk ki \(k\) elemet úgy, hogy a sorrend ne számítson.Nézzünk egy egyszerű példát. Ha kiválasztottuk az \(a\), \(b\), \(c\) elemeket, akkor rendezetten ezek a következőképpen írhatók fel:
- \(abc\) - \(acb\) - \(bac\) - \(bca\) - \(cab\) - \(cba\)
Összesen 6 különböző sorrendet kaptunk, vagyis \(3!=6\)-ot. De ezek mind ugyanahhoz az egyetlen kombinációhoz tartoznak, nevezetesen ahhoz a háromelemű részhalmazhoz, amelynek elemei \(a\), \(b\), \(c\).
Általánosan bármely kiválasztott \(k\) elem pontosan \(k!\) különböző módon rendezhető sorba. Egy ötelemű kiválasztás például \(5!=120\) különböző sorrendet adna, egy két elemű kiválasztás pedig \(2!=2\)-t. Ha tehát a rendezett kiválasztásokat megszámoltuk, akkor minden valódi kombinációt éppen \(k!\)-szor vettünk figyelembe.
Ezért a sorrend nélküli kiválasztások számát úgy kapjuk meg, hogy a rendezett kiválasztások számát elosztjuk \(k!\)-lal:
\[ \binom{n}{k}=\frac{\frac{n!}{(n-k)!}}{k!} \]
Ennek egyszerűsítése után kapjuk:
\[ \binom{n}{k}=\frac{n!}{k!(n-k)!} \]
Ez a keresett bizonyítás lényege. A képlet tehát nem más, mint két világos gondolat egymásutánja:
1. megszámoljuk a sorrenddel történő kiválasztásokat; 2. elosztjuk azok számával, ahányféleképpen ugyanaz a kiválasztott \(k\) elem sorba rendezhető.
A bizonyítás logikai felépítése lépésről lépésre
Érdemes ezt a gondolatmenetet még szigorúbban is megfogalmazni. Jelölje \(V\) a rendezett, ismétlés nélküli \(k\)-elemű kiválasztások számát, és \(K\) a kombinációk számát. Az előzőek szerint:\[ V=\frac{n!}{(n-k)!} \]
Másrészt minden egyes kombinációhoz pontosan \(k!\) darab rendezett alak tartozik, és két különböző kombinációnak nincs közös rendezett alakja. Ez azért fontos, mert így a rendezett kiválasztások halmaza diszjunkt részekre bontható, ahol minden rész egy-egy kombinációhoz tartozik, és minden ilyen rész mérete \(k!\).
Ezért fennáll az összefüggés:
\[ V=K\cdot k! \]
Innen pedig közvetlenül következik:
\[ K=\frac{V}{k!}=\frac{n!}{k!(n-k)!} \]
Ez a levezetés teljes, hiszen megmutatja egyrészt a rendezett számolás módját, másrészt azt is, miért osztunk éppen \(k!\)-lal, nem többel és nem kevesebbel.
Konkrét példa: 5 tanulóból 2 kiválasztása
A matematikai bizonyítások gyakran akkor válnak igazán világossá, ha egy konkrét példán is végiggondoljuk őket. Tegyük fel, hogy egy ötfős szakköri csoportból két tanulót kell kiválasztani egy városi versenyre. Legyen az öt tanuló neve röviden: A, B, C, D, E.Ha a sorrend számítana, akkor az első helyre 5 lehetőségünk volna, a másodikra pedig már csak 4, tehát összesen:
\[ 5\cdot4=20 \]
rendezett kiválasztás létezne.
Ha azonban a kétfős csapatban a sorrend nem számít, akkor az \(AB\) és a \(BA\) eset ugyanazt jelenti. Minden kételemű kiválasztás pontosan \(2!=2\) rendezett alakban jelenik meg. Ezért a valódi kombinációk száma:
\[ \frac{20}{2}=10 \]
Ellenőrizhetjük a képlettel is:
\[ \binom{5}{2}=\frac{5!}{2!\cdot3!}=\frac{120}{2\cdot6}=10 \]
A két eredmény egyezik, tehát a gondolatmenet helyes. Ez a példa azért is hasznos, mert kézzelfoghatóvá teszi: a képlet nem valamiféle trükk, hanem a túlszámolás kijavítása.
A képlet jelentősége az iskolai matematikában
A \(\binom{n}{k}=\dfrac{n!}{k!(n-k)!}\) összefüggés az egyik legfontosabb formula a középiskolai kombinatorikában. A magyar matematikaoktatásban is sokféle témához kapcsolódik. Először rendszerint egyszerű kiválasztási feladatokban jelenik meg, később azonban valószínűségszámítási példákban, binomiális tételben, sőt a Pascal-háromszög értelmezésében is alapvető szerepet kap.Ha például azt kérdezzük, hányféleképpen lehet kiválasztani 3 diákot egy 30 fős osztályból, akkor a válasz:
\[ \binom{30}{3}=\frac{30!}{3!\cdot27!} \]
Ilyenkor senki sem kezdi el kézzel felsorolni az eseteket; a képlet gyors és pontos számítást ad. Hasonlóan, amikor a lottó esélyeiről beszélünk, vagy egy tesztben azt számoljuk, hányféleképpen lehet kiválasztani bizonyos válaszokat, ugyanez a gondolat kerül elő.
A binomiális együtthatók a Newton-féle binomiális tételben is megjelennek, például \((a+b)^n\) kifejtésekor. Ott a \(\binom{n}{k}\) szám azt mutatja meg, hányféleképpen választhatjuk ki a szorzatban az \(a\)-k és \(b\)-k megfelelő kombinációját. Ez is jól mutatja, hogy a kombinációk száma nem elszigetelt témakör, hanem több matematikai fejezetet összekötő alapfogalom.
Gyakori hibák és félreértések
A diákok körében több tipikus hiba is előfordul ennél a témánál. Az első és leggyakoribb, hogy nem döntik el pontosan, számít-e a sorrend. Pedig ez a legelső kérdés kell legyen minden kombinatorikai feladatban. Ha számít a sorrend, variációról van szó; ha nem, akkor kombinációról. Sok rossz megoldás abból keletkezik, hogy valaki automatikusan a „választás” szóra kombinációt alkalmaz, holott a feladat valójában szerepeket is kioszt, tehát sorrendet is megkülönböztet.A másik gyakori probléma a faktoriális kezelésében jelentkezik. A tanuló néha látja ugyan a képletet, de nem érti, miért marad meg a számlálóban bizonyos tényező, és miért egyszerűsödik ki másik. Holott ha valaki tudja, hogy
\[ n!=n\cdot(n-1)\cdot(n-2)\cdots1, \]
akkor könnyen beláthatja, hogy
\[ \frac{n!}{(n-k)!}=n\cdot(n-1)\cdots(n-k+1). \]
A harmadik félreértés az ismétlés kérdése. A bizonyításunk csak akkor érvényes ebben a formában, ha az elemek különbözők, és ugyanazt az elemet nem választjuk ki többször. Ha ismétléses kiválasztásról volna szó, más módszerre lenne szükség. Ezért a feladat szövegének pontos értelmezése itt is nélkülözhetetlen.
Miért fontos a bizonyítás megértése, nemcsak a képlet ismerete?
Az iskolai matematika egyik örök kérdése, hogy elég-e tudni egy képletet, vagy érteni is kell, hogyan jön létre. A kombinációk esetében különösen igaz, hogy az igazi biztonságot a megértés adja. Ha valaki csak annyit tud, hogy „ilyen feladatnál ezt kell beírni”, akkor könnyen összekeverheti a kombinációt a variációval vagy a permutációval. Ha viszont látja a logikát, akkor új helyzetekben is el tud igazodni.A bizonyítás szépsége abban áll, hogy nagyon természetes. Előbb számolunk egy egyszerűbben kezelhető mennyiséget, majd észrevesszük, hogy ebben minden esetet többször vettünk figyelembe. Ezután a fölösleges ismétlődéseket osztással eltávolítjuk. Ez a fajta gondolkodás a matematika sok más területén is hasznos: gyakran nem közvetlenül azt számoljuk, amire kíváncsiak vagyunk, hanem valami rokon dolgot, majd abból következtetünk a keresett eredményre.
Összegzés
Bebizonyítottuk, hogy az \(n\) különböző elem közül kiválasztható \(k\) elemű kombinációk száma valóban\[ \binom{n}{k}=\frac{n!}{k!(n-k)!}. \]
A bizonyítás menete röviden a következő volt. Először megszámoltuk a rendezett kiválasztásokat: ezek száma
\[ \frac{n!}{(n-k)!}. \]
Ezután felismertük, hogy egyetlen \(k\) elemű kombináció pontosan \(k!\) különböző sorrendben írható fel. Mivel tehát minden kombinációt \(k!\)-szor számoltunk meg, a helyes eredményt úgy kapjuk, hogy a rendezett kiválasztások számát elosztjuk \(k!\)-lal. Így jutunk el a végső képlethez:
\[ \binom{n}{k}=\frac{n!}{k!(n-k)!}. \]
Ez az összefüggés nemcsak a kombinatorika egyik alaptétele, hanem a matematikai gondolkodás szép példája is. Megmutatja, hogy egy látszólag bonyolult formula mögött egyszerű és világos logika rejlik. Éppen ezért érdemes nem pusztán megtanulni, hanem valóban megérteni. Ha ezt sikerül belátni, akkor a kombinációk képlete többé nem idegen szabály lesz, hanem egy természetes következmény, amelyet bármikor újra fel tudunk építeni gondolatban.
Értékelje:
Jelentkezzen be, hogy értékelhesse a munkát.
Bejelentkezés