kombinaatsiooni

Kombinaatsioon ehk valik hulgast, kus järjestus ei mängi rolli, on põhikontseptsioon kombinatoorikas. Kui on hulk n erinevat elementi ja soovitakse valida neist k elementi ilma kordusteta, nimetatakse selle valiku arvuks kombinatsioonide arvu ning seda tähistatakse sageli C(n, k) või n valitud k-ga. Kombinatsioonide arv on võrreldav faktoriialde jagatuna k- ja (n − k)- faktoriaalidega: C(n, k) = n! / (k!(n − k)!). Kui k > n, on tulem null.

Kombinatsioonide tüüpe on mitu. Ilma kordusteta kombinatsioonid tähistavad valikuid, kus iga element võib esineda vaid üks kord. Kordustega kombinatsioonide korral võib sama elementi valida mitu korda, mille arv on C(n + k − 1, k). Need nimetatakse sageli multiset-kombinatsioonideks ja lahendatakse vahel ka stars-and-bars meetodil.

Kombinatsioonid erinevad permutationitest, kus järjestus loeb. Permutatsioonide arv on n! / (n − k)!, sõltuvalt sellest, kas järjekord on tähtis või mitte. Näide: hulgast {A, B, C, D} valida kolm elementi ilma kordusteta, annab C(4, 3) = 4 erinevat kombinatsiooni (nt ABC, ABD, ACD, BCD).

Rakendused ulatuvad tõenäosusest ja statistikast loendusteni, kombinatoorsete skeemide ja eksperimentide disainini ning mängude ja kaartide analüüsimiseni. Ajalooliselt on kombinatoorika arenenud läbi Pascaluse kolmnurga ja binomiaalteoreemi, kuid selle ideed ulatuvad veel vanemasse matemaatikasse. Kombinaatsioonide mõistmine on keskne vahend arvuliste probleemide lahendamisel ning tõenäosuslikus andmetöötluses.