Kombinatorisk søgning er søgning og optælling af antallet af kombinationer, der kan laves ud fra givne elementer, mens givne forhold overholdes. Det bruges til at løse problemer med sandsynlighedsteori og matematisk statistik.
Eksempel nr. 1 (den enkleste kombinatoriske søgning): 6 elever deltager i konkurrencen, lad os betegne dem 1,2,3,4,5,6. Hvordan kan pladserne fordeles blandt deltagerne i konkurrencen? (1,2,3,4,5,6) (3,5,6,1,2,4) (2,4,3,1,6,5) Der er præcis lige så mange muligheder, som der er permutationer af seks numre.
Eksempel #2: Samme opgave, men nu er der tre præmier til 6 deltagere. Måske vil præmier blive fordelt 4,6,1 eller 5,2,3, det er indlysende, at der kan være præcis lige så mange fordelingsmuligheder i top tre, som der er måder at vælge tre numre ud af seks.
Eksempel nr. 3: Vi komplicerer opgaven, når det bliver muligt for deltagerne at tage 1, 2 eller 3 præmier. Nu skal vi ikke kun overveje mulighederne, når deltageren kommer i top tre, men også hvordan 1., 2. og 3. pladserne fordeles blandt vinderne.
De enkleste kombinationer, som kombinatorisk søgning beskæftiger sig med, er kombinationer, placeringer, permutationer .
En kombination af n elementer med m for 1 ≤ m ≤ n er enhver kombination, der kombinerer m af nogle elementer fra antallet af givne n elementer. To sådanne kombinationer anses for forskellige, hvis nogen af de givne n elementer er inkluderet i en af dem, men ikke inkluderet i den anden kombination.
Et arrangement af n elementer med m for 1 ≤ m ≤ n er enhver kombination, der kombinerer i en bestemt rækkefølge m af alle elementer blandt de givne n elementer. To sådanne kombinationer anses for forskellige, hvis de adskiller sig enten i deres sammensætning eller i rækkefølgen af deres bestanddele. Eller begge.
At placere n elementer over n elementer kaldes en permutation fra givne n elementer .
Der er to hovedprincipper:
Lad os antage, at dette eller hint problem løses ved enhver af k metoder, og den første metode kan anvendes på n 1 måder, den anden metode på n 2 måder, ……., k-th metode på n k måder. Så er problemet løst n 1 + n 2 + ……. n k måder.
Antag, at et bestemt problem løses i k på hinanden følgende trin, og antallet af måder at løse problemet på i hvert næste trin ikke afhænger af, hvilke mulige måder det blev løst på alle tidligere trin, og er n 1 måder på det første trin, n 2 på andet trin …n k måder på kth trin. To løsninger anses for forskellige, hvis de opnås forskelligt i det mindste på et af stadierne. Under disse forhold kan problemet løses på n 1 * n 2 * ····· n k måder.