Kombinatorikai feladatnál először azt mondd meg, mit tekintesz különböző eredménynek. A csapattagokat személy szerint különböztetjük meg; a mintacsomagnál azonos típusú darabok felcserélése ugyanazt az összetételt hagyja meg. Ezután két kérdés segít képletet választani: számít-e a kiválasztott elemek sorrendje, és előfordulhat-e ugyanaz a lehetőség többször? Egy csapat névsora, egy előadási sorrend és egy ismétlődő jeleket megengedő kód így azonos elemszám mellett is eltérő feladat.
Kilenc jelentkezőből három résztvevő
Szemléltető példánkban kilenc különböző jelentkezőből háromfős csoportot választunk. Egy személy csak egyszer szerepelhet, és a csoporton belüli felsorolási sorrend lényegtelen. Ez ismétlés nélküli kombináció.
C(n, k) = n! / (k! × (n − k)!).
A felkiáltójel faktoriálist jelent: az adott pozitív egésztől egyig tartó egész számok szorzatát. A kombináció képletét és a sorrend nélküli kiválasztás értelmezését a Python matematikai dokumentációja is rögzíti.
A példában 9 × 8 × 7 = 504 rendezett hármast lehetne kialakítani. Ugyanazt a háromfős csoportot 3 × 2 × 1 = 6 sorrendben sorolhatjuk fel. Ezért 504 / 6 = 84 különböző csoport marad.
Ha három külön szerepet osztasz ki
Ha a három hely az első, második és harmadik előadót jelenti, a sorrend már számít. Az első helyre kilenc, a másodikra nyolc, a harmadikra hét ember közül választhatsz. Az eredmény 9 × 8 × 7 = 504.
Ez ismétlés nélküli variáció, általánosan n! / (n − k)!. A különbség a csoportkiválasztáshoz képest pontosan a három hely hatféle sorrendje. A kombinatorika-kalkulátorban ezért a variáció módot válaszd, amikor a kiosztott helyek vagy szerepek megkülönböztethetők.
Ha mind a kilenc embert teljes sorba rendezed, már kilenc elem permutációját számolod: 9! = 362 880. A három szerep kiosztása és a teljes sorbarendezés így külön bemenetet jelent.
Ismétlődhet ugyanaz a lehetőség?
Vegyünk kilenc különböző jelet, és készítsünk hárompozíciós jelöléseket. Ha minden pozícióra bármelyik jel kerülhet, mindhárom helyen kilenc választás van. A számuk 9³ = 729. Ez ismétléses variáció. A jelöléseknél minden pozíció megmarad; egy esetleges kezdő nulla is a kód része.
Másik helyzetben kilencféle azonos méretű mintából három darabot kérünk, a típusok ismétlődhetnek, a csomagon belüli sorrend pedig közömbös. Az ismétléses kombináció képlete pozitív n mellett:
C(n + k − 1, k).
A példában C(11, 3) = 11 × 10 × 9 / 6 = 165 különböző összetétel. A SciPy kombinációs dokumentációja külön kezeli az ismétlést megengedő változatot is. A képlet azt feltételezi, hogy bármelyik típusból rendelkezésre áll a szükséges darabszám.
| Feladat | Sorrend számít? | Ismétlés lehet? | Eredmény |
|---|---|---|---|
| Háromfős csoport | Nem | Nem | 84 |
| Három előadási hely | Igen | Nem | 504 |
| Hárompozíciós jelölés | Igen | Igen | 729 |
| Háromdarabos mintacsomag | Nem | Igen | 165 |
Legalább egy új résztvevő legyen a csoportban
A kilenc jelentkező közül most négy új és öt tapasztalt. Háromfős csoportot választunk, a sorrend nem számít, és legalább egy új résztvevő szükséges. Az összes 84 csoportból azokat kell kivonni, amelyek kizárólag az öt tapasztalt jelentkezőből állnak.
Megfelelő csoportok = C(9, 3) − C(5, 3) = 84 − 10 = 74.
A feltételt másik bontással is ellenőrizheted:
| Új résztvevők száma | Tapasztaltak száma | Csoportok száma |
|---|---|---|
| 1 | 2 | C(4, 1) × C(5, 2) = 40 |
| 2 | 1 | C(4, 2) × C(5, 1) = 30 |
| 3 | 0 | C(4, 3) × C(5, 0) = 4 |
A három sor kizárja egymást, és minden megfelelő csoportot lefed: 40 + 30 + 4 = 74. A „legalább egy” feltétel tehát eltér a „pontosan egy” feltételtől, amelyhez csak az első sor 40 csoportja tartozik.
A kalkulátorral a külön kombinációkat számold ki, majd az itt leírt kivonást vagy szorzásokat végezd el. Ez nem új feltételmező az eszközben. Bonyolultabb szabálynál előbb olyan esetekre bontsd a feladatot, amelyek nem fedik át egymást; így elkerülhető ugyanannak a csoportnak a többszöri beszámítása.
A lehetőségek darabszáma még nem ad egyenlő esélyt
A kilenc jelből háromszor, egymástól függetlenül és visszatevéssel húzott sorozatnak 729 egyformán valószínű eredménye van, ha minden jel minden húzáskor egyenlő esélyű. Ha ezután elfelejted a sorrendet, 165 különböző összetétel marad, de ezek már eltérő esélyűek.
Az AAA összetételt egyetlen sorozat adja: valószínűsége 1/729. Három különböző, előre kijelölt jel, például A, B és C összetétele hat sorrendből állhat elő, így esélye 6/729. A két összetétel közül a második hatszor valószínűbb ebben a húzási eljárásban.
Az 1/165 valószínűség csak olyan külön kiválasztási szabálynál volna indokolt, amely a 165 összetételből választ egyenletesen. Valószínűség számításakor ezért a sorsolás módját is írd le: a számlálási képlet és az egyenlő esélyű elemi kimenetelek kiválasztása két külön lépés.
Mikor kell további feltételt hozzáadni?
Ha két ember nem lehet egy csoportban, az alapképlet még túl sok lehetőséget számol. Ha egy mintatípusból csak egy darab áll rendelkezésre, a korlátlan ismétlés feltétele már nem teljesül. Ilyenkor bontsd a feladatot külön esetekre, vagy vond le a kizárt esetek számát úgy, hogy az átfedéseket is kezeld.
Ismétlés nélkül kilenc különböző elemből tízet kiválasztani lehetetlen: a lehetőségek száma nulla. Nulla elem kiválasztásának matematikailag egy módja van, az üres kiválasztás; ehhez kapcsolódik a 0! = 1 megállapodás. Negatív vagy tört elemszám ezekben a darabszámfeladatokban értelmetlen.
A kalkulátor eredményét pontos egész számként tartsd meg. A nagyon hosszú szám kerekítése szemléltetéshez hasznos lehet, de további kombinatorikai művelethez az egész értéket használd. A megoldás elejére írd oda, mi számít különböző kimenetelnek, mi a sorrend szerepe, és megengedett-e az ismétlés. Ebből derül ki, hogy valóban a feladathoz tartozó számot kaptad-e.
Záró tudáspróba
Kérdésenként egy választ jelölj meg, majd a megoldások alapján pontozd magad. Ez a három kérdés a cikkben bemutatott összefüggéseket ellenőrzi.
1. Kilenc különböző emberből három különböző előadási helyet töltesz be, emberenként legfeljebb egy hellyel. Hány kiosztás van?
- A) 504.
- B) 729.
- C) 84.
2. Négy új és öt tapasztalt jelentkezőből háromfős csoportot választasz, legalább egy új résztvevővel. Hány csoport megfelelő?
- A) 74.
- B) 40.
- C) 84.
3. Kilenc jelből három független, egyenletes húzás után elfelejted a sorrendet. Az előre rögzített ABC összetétel mennyivel valószínűbb az AAA-nál?
- A) Hatszor valószínűbb.
- B) Kilencszer valószínűbb.
- C) Ugyanolyan valószínű.
Megoldások és pontozás
1. A. A szerepek megkülönböztethetők, és ismétlés nincs: 9 × 8 × 7 = 504. Ismétléshez: Ha három külön szerepet osztasz ki.
2. A. Az összes C(9,3) = 84 csoportból C(5,3) = 10 kizárólag tapasztalt csoportot kivonunk. A pontosan egy új résztvevő más feltétel. Ismétléshez: Legalább egy új résztvevő legyen a csoportban.
3. A. AAA egyetlen, ABC hat különböző rendezett sorozatból áll elő. Mindegyik sorozat esélye 1/729. Ismétléshez: A lehetőségek darabszáma még nem ad egyenlő esélyt.
Minden helyes válasz 1 pont; a hibás vagy kihagyott válasz 0 pont. Az összpontszám 0–3 lehet.
- 0 pont: dolgozd végig újra a három megoldásban megjelölt részt, és írd le a példák kiinduló feltételeit.
- 1 pont: a két elhibázott kérdésnél vezesd le a helyes választ; külön írd mellé, melyik feltétel vagy számolási lépés maradt ki.
- 2 pont: térj vissza az egyetlen elhibázott kérdéshez kapcsolt részhez, majd egy bemenet megváltoztatásával ellenőrizd újra az eredményt.
- 3 pont: a három összefüggést ebben a feladatsorban helyesen alkalmaztad. Próbáld ki a cikk egyik ellenőrzését saját adatokkal, a feltételeket és a mértékegységeket is feljegyezve.