Kombinatorické vyhledávání je vyhledávání a počítání počtu kombinací, které lze z daných prvků vytvořit při dodržení daných podmínek. Používá se při řešení problémů teorie pravděpodobnosti a matematické statistiky.
Příklad č. 1 (nejjednodušší kombinatorické hledání): Soutěže se účastní 6 studentů, označme je 1,2,3,4,5,6. Jak lze rozdělit místa mezi účastníky soutěže? (1,2,3,4,5,6) (3,5,6,1,2,4) (2,4,3,1,6,5) Existuje přesně tolik možností, kolik je permutací šest čísel.
Příklad č. 2: Stejný úkol, ale nyní jsou tři ceny pro 6 soutěžících. Možná se ceny budou rozdávat 4,6,1 nebo 5,2,3, je zřejmé, že v první trojici může být přesně tolik možností distribuce, kolik je způsobů, jak vybrat tři čísla ze šesti.
Příklad č. 3: Úkol zkomplikujeme, když je možné, aby soutěžící získali 1, 2 nebo 3 ceny. Nyní je potřeba zvážit nejen možnosti, kdy se účastník dostane do první trojky, ale také to, jak se mezi vítěze rozdělí 1., 2. a 3. místa.
Nejjednodušší kombinace, kterými se kombinatorické vyhledávání zabývá, jsou kombinace, umístění, permutace .
Kombinace n prvků podle m pro 1 ≤ m ≤ n je jakákoli kombinace, která kombinuje m některých prvků z počtu daných n prvků. Dvě takové kombinace jsou považovány za různé, pokud je některý z daných n prvků zahrnut v jedné z nich, ale není zahrnut v druhé kombinaci.
Uspořádání n prvků podle m pro 1 ≤ m ≤ n je jakákoli kombinace, která kombinuje v určitém řádu m libovolných prvků z daných n prvků. Dvě takové kombinace jsou považovány za odlišné, pokud se liší buď svým složením, nebo pořadím prvků, které je tvoří. Nebo oboje.
Umístění n prvků na n prvků se nazývá permutace z daných n prvků .
Existují dva hlavní principy:
Předpokládejme, že ten či onen problém je řešen některou z k metod, přičemž první metoda může být aplikována n 1 způsoby, druhá metoda n 2 způsoby, ……., k-tá metoda n k způsoby. Potom je úloha vyřešena n 1 + n 2 + ……. n k způsoby.
Předpokládejme, že konkrétní problém je řešen v k po sobě jdoucích fázích a počet způsobů řešení problému v každé další fázi nezávisí na tom, jakými možnými způsoby byl řešen ve všech předchozích fázích, a v první fázi je n 1 způsobů, n 2 na druhém stupni …n k cest na k-tém stupni. Dvě řešení jsou považována za odlišná, pokud jsou získána odlišně alespoň v jedné z fází. Za těchto podmínek lze problém vyřešit n 1 * n 2 * ····· n k způsoby.