A kombinatorikus keresés az adott elemekből az adott feltételek betartásával készíthető kombinációk keresése és megszámlálása. Valószínűségszámítási és matematikai statisztikai problémák megoldására használják.
1. számú példa (a legegyszerűbb kombinatorikus keresés): 6 tanuló vesz részt a versenyen, jelöljük őket 1,2,3,4,5,6-tal. Hogyan lehet a helyeket elosztani a verseny résztvevői között? (1,2,3,4,5,6) (3,5,6,1,2,4) (2,4,3,1,6,5) Pontosan annyi opció van, ahány permutáció hat szám.
2. példa: Ugyanaz a feladat, de most három nyeremény jár 6 versenyző számára. Lehet, hogy 4,6,1 vagy 5,2,3 lesz a nyeremények kiosztása, nyilvánvaló, hogy az első háromban pontosan annyi kiosztási lehetőség lehet, ahány szám közül lehet hármat kiválasztani a hatból.
3. példa: Bonyolítjuk a feladatot, ha a versenyzők 1, 2 vagy 3 díjat nyerhetnek. Most nem csak azt kell mérlegelnünk, hogy mikor kerül a résztvevő az első háromba, hanem azt is, hogy az 1., 2. és 3. helyezés hogyan oszlik meg a nyertesek között.
A legegyszerűbb kombinációk, amelyekkel a kombinatorikus keresés foglalkozik, a kombinációk, elhelyezések, permutációk .
Az n elem m-nek megfelelő kombinációja 1 ≤ m ≤ n esetén bármely olyan kombináció, amely egyesíti az adott n elem számából néhány elem m-ét. Két ilyen kombinációt akkor tekintünk különbözőnek, ha az adott n elem közül valamelyik szerepel az egyikben, de a másik kombinációban nem.
Egy n elem m-vel való elrendezése 1 ≤ m ≤ n esetén bármely olyan kombináció, amely meghatározott sorrendben egyesíti m elemét az adott n elem közül. Két ilyen kombinációt akkor tekintünk különbözőnek, ha összetételükben vagy alkotóelemeik sorrendjében különböznek. Vagy mindkettő.
Ha n elemet n elem fölé helyezünk , azt permutációnak nevezzük adott n elemből .
Két fő elv van:
Tegyük fel, hogy ezt vagy azt a problémát k módszer bármelyike megoldja, és az első módszer n 1 , a második módszer n 2 , ……., a k-edik módszer n k módon alkalmazható. Ekkor a feladat megoldva n 1 + n 2 + ……. n k módon.
Tegyük fel, hogy egy adott problémát k egymást követő szakaszban oldanak meg, és a probléma megoldásának módjainak száma az egyes következő szakaszokban nem függ attól, hogy melyik lehetséges módon oldották meg az összes előző szakaszban, és n 1 megoldás az első szakaszban, n 2 a második szakaszban …n k módon a k-adik szakaszban. Két megoldást akkor tekintünk különbözőnek, ha legalább az egyik szakaszban eltérően kapják meg őket. Ilyen feltételek mellett a probléma n 1 * n 2 * ····· n k módon megoldható.