La búsqueda combinatoria es la búsqueda y el conteo del número de combinaciones que se pueden hacer a partir de elementos dados, mientras se observan condiciones dadas. Se utiliza en la resolución de problemas de teoría de la probabilidad y estadística matemática.
Ejemplo No. 1 (la búsqueda combinatoria más simple): 6 estudiantes participan en la competencia, denotemos 1,2,3,4,5,6. ¿Cómo se pueden repartir las plazas entre los participantes en el concurso? (1,2,3,4,5,6) (3,5,6,1,2,4) (2,4,3,1,6,5) Hay exactamente tantas opciones como permutaciones de seis numeros
Ejemplo #2: La misma tarea, pero ahora hay tres premios para 6 concursantes. Tal vez los premios se distribuyan 4,6,1 o 5,2,3, es obvio que puede haber exactamente tantas opciones de distribución en los tres primeros como formas de elegir tres números de seis.
Ejemplo No. 3: Complicamos la tarea cuando se hace posible que los concursantes se lleven 1, 2 o 3 premios. Ahora debemos considerar no solo las opciones cuando el participante se ubica entre los tres primeros, sino también cómo se distribuirán los lugares 1, 2 y 3 entre los ganadores.
Las combinaciones más simples que trata la búsqueda combinatoria son combinaciones, ubicaciones, permutaciones .
Una combinación de n elementos por m para 1 ≤ m ≤ n es cualquier combinación que combina m de algunos elementos del número de n elementos dados. Dos de estas combinaciones se consideran diferentes si alguno de los n elementos dados está incluido en una de ellas, pero no incluido en la otra combinación.
Un arreglo de n elementos por m para 1 ≤ m ≤ n es cualquier combinación que combina en cierto orden m de cualquier elemento de entre los n elementos dados. Dos de estas combinaciones se consideran diferentes si difieren en su composición o en el orden de sus elementos constituyentes. O ambos.
La colocación de n elementos sobre n elementos se denomina permutación a partir de n elementos dados .
Hay dos principios fundamentales:
Supongamos que este o aquel problema se resuelve con cualquiera de los k métodos, y el primer método se puede aplicar de n 1 formas, el segundo método de n 2 formas, ……., k-ésimo método de n k formas. Entonces el problema se resuelve n 1 + n 2 + ……. n k maneras.
Suponga que un problema en particular se resuelve en k etapas sucesivas, y la cantidad de formas de resolver el problema en cada etapa siguiente no depende de las formas posibles en que se resolvió en todas las etapas anteriores, y es de n 1 formas en la primera etapa, n 2 en la segunda etapa …n k vías en la k-ésima etapa. Dos soluciones se consideran diferentes si se obtienen de manera diferente al menos en una de las etapas. En estas condiciones, el problema se puede resolver de n 1 * n 2 * ····· n k maneras.