Kombinatorikai feladatnál két kérdés dönt a képletről: 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 külön feladat. Az elemek száma lehet azonos, az eredmények mégis jelentősen eltérhetnek.
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 |
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 pedig írd oda a két döntést: a sorrend szerepét és az ismétlés megengedését. Ebből derül ki, hogy valóban a feladathoz tartozó számot kaptad-e.