Kombinatorinen haku on annetuista elementeistä tehtävien yhdistelmien etsimistä ja laskemista tiettyjä ehtoja noudattaen. Sitä käytetään todennäköisyysteorian ja matemaattisten tilastojen ongelmien ratkaisemiseen.
Esimerkki nro 1 (yksinkertaisin kombinatorinen haku): Kilpailuun osallistuu 6 opiskelijaa, merkitään heille 1,2,3,4,5,6. Miten paikat jaetaan kilpailun osallistujien kesken? (1,2,3,4,5,6) (3,5,6,1,2,4) (2,4,3,1,6,5) Vaihtoehtoja on tasan niin monta kuin on permutaatioita kuusi numeroa.
Esimerkki 2: Sama tehtävä, mutta nyt on kolme palkintoa kuudelle kilpailijalle. Ehkä palkintoja jaetaan 4,6,1 tai 5,2,3, on selvää, että kolmen parhaan joukossa voi olla täsmälleen yhtä monta jakovaihtoehtoa kuin on mahdollista valita kolme numeroa kuudesta.
Esimerkki nro 3: Monimutkaistamme tehtävää, kun kilpailijat voivat voittaa 1, 2 tai 3 palkintoa. Nyt meidän on pohdittava paitsi vaihtoehtoja, milloin osallistuja pääsee kolmen parhaan joukkoon, myös sitä, kuinka 1., 2. ja 3. sijat jaetaan voittajien kesken.
Yksinkertaisimmat yhdistelmät, joita kombinatorinen haku käsittelee, ovat yhdistelmät, sijoittelut, permutaatiot .
N alkion yhdistelmä m:llä arvolla 1 ≤ m ≤ n on mikä tahansa yhdistelmä, joka yhdistää m joistakin alkioista annetun n elementin lukumäärästä. Kahta tällaista yhdistelmää pidetään erilaisina, jos jokin annetuista n elementistä sisältyy yhteen niistä, mutta ei sisälly toiseen yhdistelmään.
N elementin järjestely m:llä arvolla 1 ≤ m ≤ n on mikä tahansa yhdistelmä, joka yhdistää tietyssä järjestyksessä m mitä tahansa alkiota annetusta n elementistä. Kahta tällaista yhdistelmää pidetään erilaisina, jos ne eroavat joko koostumukseltaan tai ainesosien järjestyksestä. Tai molemmat.
N elementin sijoittamista n elementin päälle kutsutaan permutaatioksi annetusta n elementistä .
On olemassa kaksi pääperiaatetta:
Oletetaan, että tämä tai tuo ongelma ratkaistaan millä tahansa k:stä menetelmästä ja ensimmäistä menetelmää voidaan soveltaa n 1 tavalla, toista menetelmää n 2 tavalla, ……., k:nnettä menetelmää n k :llä tavalla. Sitten ongelma on ratkaistu n 1 + n 2 + ……. n k tapaa.
Oletetaan, että tietty ongelma ratkaistaan k peräkkäisessä vaiheessa ja kuinka monta tapaa ratkaista ongelma kussakin seuraavassa vaiheessa ei riipu siitä, millä mahdollisilla tavoilla se on ratkaistu kaikissa aikaisemmissa vaiheissa, ja on n 1 tapaa ensimmäisessä vaiheessa, n 2 toisessa vaiheessa …n k tapaa k:nnessä vaiheessa. Kaksi ratkaisua katsotaan erilaisiksi, jos ne saadaan eri tavalla ainakin yhdessä vaiheessa. Näissä olosuhteissa ongelma voidaan ratkaista n 1 * n 2 * ····· n k tavalla.