Amikor kombinatorikában számolunk, akkor miért kell összeszorozni a számokat?

#1 jót mond, de abból csak az látszik, miért csökkennek a számok, az nem, hogy miért kell összeszorozni őket.

Nézzük csak azt az egyszerűbb esetet, hogy az 5-ből kettőt teszünk magunk elé és számít az is, melyik kerül balra, és melyik jobbra. Az fog kijönni, hogy ez 5·4-féle módon mehet:

Tegyünk egyet a bal oldalra, ez 5-féle lehet. Bármelyiket is tettük oda, marad még 4 labda, tehát a jobb oldalra 4-féle labda közül tehetünk egyet. Miért szorozni kell az 5-öt és a 4-et és miért nem mondjuk összeadni?

Bármelyik labda is került a bal oldalra, 4-féle lehet a jobb oldalon. Vagyis ha "A" van balra, akkor is 4 lehet jobbra, ha "B" van, akkor is, ha "C" van, akkor is 4, stb, mind az ötnél. Ez tehát 4+4+4+4+4 vagyis 5·4 lehetőség.

Fel is tudjuk sorolni őket:

Ha "A" van balra, akkor: AB, AC, AD, AE

Ha "B" van balra, akkor: BA, BC, BD, BE

Aztán CA, CB, CD, CE

Aztán DA, DB, DC, DE

Végül EA, EB, EC, ED

OK?

(Az egy teljesen más dolog, hogy mikor és miért kell osztani mondjuk 3 faktoriálissal...)

Megadunk egy eljárást, amelyet követve fel lehet írni az eseteket, és amely egyszerű képletet szolgáltat a darabszámra. Az eljárás pedig általánosan, (n-ből kiválasztunk k-t) esetén (most: (5-ből kiválasztunk 3-at)) a következő.

Először felírjuk az összes k hosszú, az n méretű halmaz elemeiből maximum 1-et tartalmazó rendezett listát. Ezekből n*(n-1)*..*(n-k+1) darab van, a variációk leszámolásából ismert logika alapján.

Az így kapott listánkban egy konkrét kiválasztás (amiket le akarunk számolni) többször is szerepel.

Kis tűnődés után rájövünk, hogy minden konkrét kiválasztás éppen #Var(k)=k!-szor szerepel.

Ekkor azt kapjuk, hogy

#Lista = k!*#(n-ből kiválasztunk k-t).

Leosztás után megkapjuk a képletet. (Ahol a 'Lista'-ban az előbbi, korlátos hosszúságú variációk szerepelnek.)

Szóval a képlet felfogható egy konkrét, trükkös leszámláló algoritmus megvalósításának. (Igazából a faktoriális maga is felfogható a variációknak egy bizonyos leszámlálási módjaként.)

(Természetesen a képlet csak egy képlet, függetlenül attól, hogyan kapjuk meg. De mivel nem nagyon szokás máshogy megkapni (rekurzióval? valszámmal, darabszámok helyett gyakoriságokat mondva? analízissel és binomiális tétellel? Stb), ezért talán tényleg érdemes lehet így ránézni, hogy két variációra vezetjük vissza a kérdést jobb híján.)