Kombinatorisk sökning är sökning och räkning av antalet kombinationer som kan göras från givna element, samtidigt som givna förutsättningar observeras. Det används för att lösa problem med sannolikhetsteori och matematisk statistik.
Exempel nr 1 (den enklaste kombinatoriska sökningen): 6 elever deltar i tävlingen, låt oss beteckna dem 1,2,3,4,5,6. Hur kan platserna fördelas mellan deltagarna i tävlingen? (1,2,3,4,5,6) (3,5,6,1,2,4) (2,4,3,1,6,5) Det finns exakt lika många alternativ som det finns permutationer av sex siffror.
Exempel #2: Samma uppgift, men nu finns det tre priser för 6 tävlande. Kanske kommer priser att delas ut 4,6,1, eller 5,2,3, det är uppenbart att det kan finnas exakt lika många fördelningsalternativ i topp tre som det finns sätt att välja tre nummer av sex.
Exempel nr 3: Vi komplicerar uppgiften när det blir möjligt för de tävlande att ta 1, 2 eller 3 priser. Nu måste vi överväga inte bara alternativen när deltagaren kommer in bland de tre bästa, utan också hur 1:a, 2:a och 3:e platserna kommer att fördelas bland vinnarna.
De enklaste kombinationerna som kombinatorisk sökning handlar om är kombinationer, placeringar, permutationer .
En kombination av n element med m för 1 ≤ m ≤ n är vilken kombination som helst som kombinerar m av vissa element från antalet givna n element. Två sådana kombinationer anses olika om något av de givna n elementen ingår i ett av dem, men inte ingår i den andra kombinationen.
Ett arrangemang av n element med m för 1 ≤ m ≤ n är vilken kombination som helst som kombinerar i en viss ordning m av alla element bland de givna n elementen. Två sådana kombinationer betraktas som olika om de skiljer sig antingen i sin sammansättning eller i ordningen av deras beståndsdelar. Eller båda.
Att placera n element över n element kallas en permutation från givna n element .
Det finns två huvudprinciper:
Låt oss anta att det här eller det problemet löses med någon av k metoder, och den första metoden kan tillämpas på n 1 sätt, den andra metoden på n 2 sätt, ……., k:te metoden på n k sätt. Då är problemet löst n 1 + n 2 + ……. n k sätt.
Antag att ett visst problem löses i k på varandra följande steg, och antalet sätt att lösa problemet i varje nästa steg inte beror på vilka möjliga sätt det löstes vid alla tidigare steg, och är n 1 sätt i det första steget, n 2 vid andra steget …n k sätt på k:te steget. Två lösningar anses olika om de erhålls olika åtminstone i ett av stegen. Under dessa förhållanden kan problemet lösas på n 1 * n 2 * ····· n k sätt.