Kombinatorika
Mielőtt képletet használunk, eldöntjük, mi számít különböző esetnek, és megmutatjuk, miért nincs kihagyás vagy többszörös számolás.
Részletes leckék és gyakorlópéldák (3) →
Alapfogalmak, példákkal
Eset és sorrend
Egy eset a feladat feltételeinek megfelelő választás. A sorrend akkor számít, ha a választott elemeknek eltérő helye vagy szerepe van.
Anna és Bence egyetlen kétfős pár. Elnök és titkár szerepben viszont kétféle kiosztásuk lehet.
Szorzási szabály
Egymást követő választásoknál az esetszámokat szorozhatjuk, ha minden korábbi választás után ugyanannyi folytatás engedett.
Három leves és két főétel közül egy-egyet választva 3 · 2 = 6 menü készül.
Ismétlés és komplementer
Tisztázni kell, újra választható-e ugyanaz az elem. A komplementer módszerben az összes megengedett esetből a kérdésnek nem megfelelő eseteket vonjuk ki.
Két betűből kétjegyű kód ismétléssel: AA, AB, BA, BB. Ismétlés nélkül csak AB és BA marad.
A lecke végére: A kombinatorikai modellt a sorrend, az ismétlés és a kiválasztás szabályai alapján állítod fel.
Értsd meg az összefüggést!
Egy képlet alkalmazása előtt tisztázd, mit tekintünk különböző esetnek. Ha öt emberből elnököt és titkárt választunk, a szerepek miatt számít a sorrend.
Ha kétfős bizottságot, akkor ugyanaz a két ember fordított felsorolásban is ugyanaz az eset.
A szorzási szabály egymás utáni döntéseket kapcsol össze. Az összeadási szabály egymást kizáró eseteket egyesít.
Ha az esetek átfednek, az egyszerű összeadás kétszer számolhat; ilyenkor az átfedést külön kell kezelni.
Ismétlésnél az is számít, hogy az azonosnak látszó elemeket megkülönböztetjük-e. Emelt szinten a képlet mellett annak indoklását is építsd fel: miből indul a számolás, és miért kell például osztani az előzetes felsorolás eredményét.
Nézzük meg egy példán!
Számít-e a sorrend?
| Feladat | Számítás | Eredmény |
|---|---|---|
| 5 emberből elnök és helyettes | 5 × 4 | 20 |
| 5 emberből kéttagú bizottság | 5 × 4 / 2 | 10 |
A legfontosabb szabályok
- Készíts rendszerezett listát, táblázatot vagy faábrát.
- Ugyanazt a lehetőséget ne számold kétszer.
- Nagyobb feladatnál számold meg a komplementert, ha az egyszerűbb.
Mintapélda és megoldás lépésről lépésre
Feladat: öt tanulóból két képviselőt választunk, külön tisztség nélkül.
1. Első és második választásként 5 · 4 = 20 sorrend lehetséges.
2. Minden pár kétszer szerepel: például Anna–Béla és Béla–Anna ugyanaz.
3. Ezért 20/2 = 10 különböző pár választható.
Részletes magyarázatok és példák
01Rendszerezett felsorolás+
Rendezett felsorolásnál rögzíts egy elemet, és járd végig az összes folytatását. Az A, B, C betűből két különböző betű sorrendben: AB, AC, BA, BC, CA, CB, összesen 6.
Ha párt választunk sorrend nélkül, csak AB, AC, BC marad.
02Táblázat és faábra+
A faábra egy-egy ága egy választást mutat; a teljes gyökértől levélig tartó út egy kimenetel. Két egymás utáni pénzfeldobás útjai: FF, FI, IF, II.
Táblázatban az első dobás a sort, a második az oszlopot jelölheti.
03Szorzási és összeadási szabály+
Ha minden első választást ugyanannyi második követhet, szorzunk: 3 felső és 4 nadrág 12 öltözet. Egymást kizáró csoportok elemszámát összeadjuk: 3 gyümölcs és 2 sütemény közül egy desszertet választva 5 lehetőség van.
Átfedő eseteket ne adj össze korrekció nélkül.
04Sorrend és ismétlés szerepe+
Az n különböző elem sorba rendezése n! lehetőség; a felkiáltójel faktoriálist jelent: 4! = 4·3·2·1 = 24, és 0! = 1. Ismétlés nélküli, sorrend nélküli k elem választása C(n,k) = n!/[k!(n−k)!].
Ismétléses k hosszú sorozat n elemből nᵏ módon készül.
05Komplementer esetek és ellenőrzés+
A komplementer az összes megengedett esetből a nem kívánt esetek halmaza. Három pénzfeldobás 8 kimeneteléből egyetlen esetben nincs fej: III.
Legalább egy fej tehát 8−1 = 7 kimenetelben van. A módszer az „egy vagy több” típusú kérdéseknél különösen hasznos.
Lépésről lépésre, részletesen
Permutáció, variáció, kombináció és binomiális tétel+
- A sorrend és ismétlés szerepét azonosítani.
- Összeszámlálást esetekre vagy komplementerre bontani.
A számlálás előtt döntsd el: minden elemet rendezünk-e, csak kiválasztunk-e, számít-e a sorrend, lehet-e ismétlés. Egymást követő független választási lehetőségek számai összeszorzódnak; egymást kizáró esetek számai összeadódnak.
Négy alaphelyzet
n különböző elem teljes rendezése n!; k elem sorrendes választása ismétlés nélkül n!/(n−k)!, ismétléssel nᵏ. Sorrend nélküli k elem választása C(n,k)=n!/[k!(n−k)!].
Ismétlődő elemek teljes rendezése n!/(r₁!…rₛ!), mert az azonos elemek belső cseréje nem ad új sorrendet.
Binomiális tétel és Pascal
(a+b)ⁿ=Σ C(n,k)aⁿ⁻ᵏbᵏ. Az együttható annak száma, hányféleképpen választunk k darab b-t az n tényezőből.
C(n,k)=C(n−1,k−1)+C(n−1,k): a kijelölt elem vagy benne van, vagy nincs a választásban. „Legalább egy” feltételnél gyakran könnyebb az összesből kivonni az egyet sem tartalmazó eseteket.
Kidolgozott példa
Öt lány és négy fiú közül háromfős bizottságot választunk. Hányban van legalább egy lány?
A bizottságban nem számít a sorrend: összesen C(9,3)=84.
A csak fiúkból álló bizottságok száma C(4,3)=4.
Legalább egy lány: 84−4=80.
- A kiválasztás és sorba rendezés eltérő modell.
Próbáld ki önállóan!
Kombinatorikai képletek és Pascal-azonosság bizonyítása+
- A fogalmat a feltételeivel együtt használni.
- A megoldást levezetni, és az eredeti feltételekkel ellenőrizni.
A számlálásnál előbb rögzítsd, megkülönböztethetők-e az elemek, számít-e a sorrend és lehet-e ismétlés. A szorzási szabály egymást követő választások lehetőségeit szorozza, az összeadási szabály egymást kizáró esetek számait adja össze.
Permutáció, variáció, kombináció
n különböző elem sorba rendezése n! lehetőség: az első helyre n, a következőre n−1,… választás. Ismétlődő elemek α₁,…,αₖ darabszámainál a megkülönböztetett példányok sorrendjeit α₁!⋯αₖ! szorzóval túl számoltuk, ezért n!/(α₁!⋯αₖ!). k helyre n különbözőből ismétlés nélkül n!/(n−k)! variáció, ismétléssel nᵏ.
Sorrend nélküli k elem kiválasztásakor minden kiválasztott halmaz k! sorrendben szerepelt: C(n,k)=n!/[k!(n−k)!].
Pascal és binomiális tétel
C(n,k)=C(n−1,k)+C(n−1,k−1): egy kiemelt elem vagy nincs a kiválasztott k elem között, vagy benne van, és a többi k−1 elemet választjuk. A Pascal-háromszög szélein 1 áll, belül a két fölötte álló szám összege. (a+b)ⁿ szorzatban k darab b választásához n tényezőből k helyet választunk, ezért a megfelelő tag C(n,k)aⁿ⁻ᵏbᵏ. k=0,…,n összeadása adja a binomiális tételt.
A képletek érvényességi feltételei
n és k nemnegatív egész. Ismétlés nélküli választásnál 0≤k≤n; 0!=1 miatt az üres választás és üres sorrend egy lehetőség.
Ismétléses permutációnál az αᵢ darabszámok összege n. Ismétléses variációnál n választható elem és k megkülönböztetett hely van.
Külön rögzítsd, hogy a helykitöltés nulla jeggyel kezdődhet-e: egy PIN-kód és egy azonos hosszú természetes szám nem ugyanaz a feladat.
Kidolgozott példa
Hány különböző sorrendben írhatók az ANANÁSZ szó betűi?
Hét betű van; A kétszer, N kétszer szerepel. Á külön betű az A-tól, S és Z is egyszeri.
A megkülönböztetett betűk 7! sorrendjéből az A-k és N-ek felcserélései nem változtatják a szót.
7!/(2!·2!)=1260. Az ékezetes Á-t nem számoljuk harmadik A-nak.
- A megengedett értékeket az átalakítás előtt rögzítsd.
- A példabeli ellenőrzés a megoldás része.
Próbáld ki önállóan!
Sorbarendezés és kiválasztás önálló modellezéssel+
- A sorrend és az ismétlés szerepét a feladatszövegből dönteni el.
- Komplementerrel és esetbontással számolni.
- Binomiális együtthatót és Pascal-sorokat előállítani.
A szorzási szabályhoz a választás szakaszait különítjük el: ha minden első döntés után ugyanannyi második lehetőség van, a számok szorzata adja az összes eredményt. Ez nem valószínűségi függetlenség állítása.
Ha az ágak különböző hosszúak, ágonként számolunk és az egymást kizáró eseteket összeadjuk.
Sorrend és ismétlés
Hat különböző könyv teljes sorrendje 6!. Három különböző tisztség betöltése hat emberből 6·5·4, mert a tisztségek megkülönböztetettek.
Háromtagú bizottság 6 emberből C(6,3)=6·5·4/3!, mert egy hármas hatféle sorrendje ugyanazt a bizottságot adja. Négy helyes kód tíz számjegyből ismétléssel 10⁴, ha a nulla kezdőjegy is megengedett.
Komplementer és kizáró esetek
Nyolc fiú és öt lány közül négyfős bizottságban legalább egy lány: C(13,4)−C(8,4). Pontosan két lány: C(5,2)·C(8,2).
Legalább két lány: a pontosan 2,3,4 lányos esetek összege. A „legalább” feltételt ne cseréld „pontosan”-ra.
Binomiális együtthatók
C(n,k)=n!/[k!(n−k)!] nemnegatív egész n,k, 0≤k≤n mellett; 0!=1. C(n,0)=C(n,n)=1 és C(n,k)=C(n,n−k), mert kiválasztott és kimaradó elemek kiegészítik egymást.
A Pascal-háromszög szélei 1-ek; minden belső elem a két fölötte levő összege: C(n,k)=C(n−1,k−1)+C(n−1,k). A két esetet egy kijelölt elem beválasztása, illetve kimaradása adja.
További Pascal-tulajdonságok
Az n-edik sor szimmetrikus, összege 2ⁿ, mert egy n elemű halmaznak ennyi részhalmaza van: minden elem bekerül vagy kimarad. n=4 sora 1,4,6,4,1; összegük 16. Az (a+b)ⁿ kifejtésében az aⁿ⁻ᵏbᵏ tag együtthatója C(n,k), mert az n tényező közül k-ból választunk b-t.
Kidolgozott példa
Hét tanulóból háromfős csapatot választunk. Anna és Béla közül legalább egyikük legyen tag.
Hány csapat lehetséges?
Sorrend nélküli választás: összesen C(7,3)=35 csapat.
A komplementerben sem Anna, sem Béla nincs: az öt másikból C(5,3)=10 csapat.
A kívánt szám 35−10=25.
Esetbontásos ellenőrzés: pontosan egyikük 2·C(5,2)=20; mindkettő C(5,1)=5; összesen 25.
- Az ágak számait csak egymást kizáró eseteknél add össze.
- A kezdő nulla megengedettségét külön ellenőrizd.
Próbáld ki önállóan!
Egy újabb kidolgozott példa
Öt emberből háromfős bizottságot választunk. Hány lehetőség van, ha minden tag szerepe azonos?
Rendezett választásban az elsőre 5, a másodikra 4, a harmadikra 3 lehetőség van: 5 · 4 · 3 = 60.
Ugyanazt a három embert 3 · 2 · 1 = 6 sorrendben soroltuk. Ezek nem külön bizottságok.
Ezért 60/6 = 10 bizottság választható. Az osztás az ismételt számolást szünteti meg.
Emelt szinten menj tovább!
Azonos tárgyak sorba rendezésekor az n! az azonos elemek felcserélését is külön számolná. Ha a típusok darabszámai k₁, k₂, …, az esetszám n!/(k₁!k₂!…).
Kombinációnál a kiválasztott elemek sorrendje nem számít. A képlet előtt mondd ki az ismétlés és sorrend feltételeit, tiltásoknál pedig használj szétválasztott eseteket vagy komplementerszámolást.
Ellenőrizd, hogy megértetted!
1. kérdés
Mennyi az esetek száma, ha a három hely különböző tisztség?
Megoldás és magyarázat
60. Ilyenkor a különböző sorrend valóban különböző szerepkiosztás, ezért nem osztunk hattal.
2. kérdés
Négy emberből elnököt és titkárt választunk. Hány kiosztás van, ha egy ember csak egy tisztséget tölthet be?
Megoldás és magyarázat
4 · 3 = 12. Az elnöknek négy, utána a titkárnak három lehetőség marad.
A szerepek miatt a sorrend számít.
3. kérdés
Hány különböző négybetűs sorrend alkotható az A, A, B, C betűkből mindegyiket felhasználva?
Megoldás és magyarázat
4!/2! = 12. A két A felcserélése nem ad új szót.
Másik út: az A-k két helyét hatféleképpen választjuk, a B és C a maradék helyeken kétféleképpen állhat: 6 · 2 = 12.