Căutarea combinatorie este căutarea și numărarea numărului de combinații care pot fi făcute din elemente date, cu respectarea condițiilor date. Este utilizat în rezolvarea problemelor de teoria probabilităților și de statistică matematică.
Exemplul nr. 1 (cea mai simplă căutare combinatorie): 6 elevi participă la concurs, să-i notăm 1,2,3,4,5,6. Cum pot fi repartizate locurile între participanții la concurs? (1,2,3,4,5,6) (3,5,6,1,2,4) (2,4,3,1,6,5) Există exact atâtea opțiuni câte permutări sunt șase numere.
Exemplul #2: Aceeași sarcină, dar acum există trei premii pentru 6 concurenți. Poate că premiile vor fi distribuite 4,6,1, sau 5,2,3, este evident că pot exista exact atâtea opțiuni de distribuire în primele trei câte modalități de a alege trei numere din șase.
Exemplul nr. 3: complicăm sarcina atunci când devine posibil ca concurenții să ia 1, 2 sau 3 premii. Acum trebuie să luăm în considerare nu numai opțiunile când participantul ajunge în primele trei, ci și modul în care locurile 1, 2 și 3 vor fi distribuite printre câștigători.
Cele mai simple combinații cu care se ocupă căutarea combinatorie sunt combinațiile, plasările, permutările .
O combinație de n elemente cu m pentru 1 ≤ m ≤ n este orice combinație care combină m ale unor elemente din numărul de n elemente date. Două astfel de combinații sunt considerate diferite dacă oricare dintre cele n elemente date este inclus în unul dintre ele, dar nu este inclus în cealaltă combinație.
Un aranjament de n elemente cu m pentru 1 ≤ m ≤ n este orice combinație care combină într-o anumită ordine m orice elemente dintre cele n elemente date. Două astfel de combinații sunt considerate diferite dacă diferă fie în compoziția lor, fie în ordinea elementelor lor constitutive. Sau amândouă.
Plasarea a n elemente peste n elemente se numește permutare din n elemente date .
Există două principii principale:
Să presupunem că aceasta sau acea problemă este rezolvată prin oricare dintre k metode, iar prima metodă poate fi aplicată în n 1 moduri, a doua metodă în n 2 moduri, ……., k-a metoda în n k moduri. Atunci problema se rezolvă n 1 + n 2 + ……. n k moduri.
Să presupunem că o anumită problemă este rezolvată în k etape succesive, iar numărul de moduri de rezolvare a problemei în fiecare etapă următoare nu depinde de modurile posibile în care a fost rezolvată în toate etapele anterioare și este de n 1 moduri la prima etapă, n 2 la a doua etapă … n k moduri la a k-a etapă. Două soluții sunt considerate diferite dacă sunt obținute diferit cel puțin la una dintre etape. În aceste condiții, problema poate fi rezolvată în n 1 * n 2 * ····· n k moduri.