Análisis combinatorio

Análisis combinatorio

1. Principios fundamentales del análisis combinatorio

   • principio de multiplicación
     • Si un evento A se puede realizar de «m» formas diferentes y luego se puede realizar otro evento B de «n» formas diferentes, el número total de formas en que pueden ocurrir A y B es igual a m x n. Es decir, ambos eventos se realizan, primero uno y luego el otro. El «y» indica multiplicación. Ejemplo: ¿de cuántas formas se puede vestir una persona que tiene 3 pantalones y 3 camisas? Para vestirse, la persona se pone el pantalón y luego la camisa, es decir tiene 3 x 3 = 9 opciones diferentes de vestirse
   • Principio de adición
     • Si un evento «A» se puede realizar de «m» maneras diferentes, y otro evento «B» se puede realizar de «n» maneras diferentes, además, si ocurre uno no puede ocurrir el otro, entonces, el evento A o el evento B, se realizarán de m+n formas. Es decir, aquí ocurre A o ocurre B. El «o» indica suma. Ejemplo: ¿de cuántas formas se puede cruzar un río, sabiendo que se dispone de 3 botes y 4 barcos? El río se puede cruzar en bote o en barco, es decir, tiene 3 + 4 = 7 opciones diferentes para cruzar el río. El río se cruza en bote o en barco.

2. variaciones

   • variaciones sin repetición
     • Variaciones sin repetición o variaciones ordinarias de m elementos tomados de n en n (de orden n)son los distintos grupos de n elementos distintos que se pueden hacer con los m elementos que tenemos, de forma que dos grupos se diferencian en algún elemento o en el orden de colocación. Se representa por Vm,n. (n≤m) Para construir las variaciones sin repetición, partimos del conjunto A={1,2,3,4} y vamos a construir todas las variaciones sin repetición posibles.
   • Variaciones con repetición
     • Variaciones con repetición de m elementos tomados de n en n (de orden n) son los distintos grupos de n elementos iguales o distintos que se pueden hacer con los m elementos que tenemos, de forma que dos grupos se diferencian en algún elemento o en el orden de colocación. Se representa por VRm,n. Para construir las variaciones con repetición, partimos del conjunto A={1,2,3,4} y vamos a construir todas las variaciones con repetición posibles.

3. combinaciones

   • Combinaciones sin repetición
     • Se entiende por combinatoria sin repetición, a los diferentes conjuntos que se pueden formar con «n» elementos, seleccionados de x en x. Cada conjunto se debe diferenciar del anterior en al menos uno de sus elementos (el orden no importa) y estos no se pueden repetir.
       • Imaginemos un pelotón militar de 12 soldados. El capitán del ejército quiere formar grupos de 2 soldados para que se infiltren tras las líneas enemigas por distintos puntos, ¿cuántos grupos distintos podría formar? Para resolver el problema, en primer lugar tenemos que identificar el número total de elementos. En este caso son 12 soldados en total, por tanto ya tenemos nuestra n. Como el capitán quiere grupos de 2, ya sabemos cual es nuestra x. Sabiendo esto, podríamos sustituir en la fórmula y tener el número de combinaciones de grupos de 2. n = 12 x = 2 Al sustituir: Aplicando el factorial para el denominador, tendríamos 12*11*10*…*1 = 479.001.600. Para el denominador tenemos 2*1*10*9*8…*1 = 7.257.600. Nuestro número combinatorio es =479.001.600/7.257.600 = 66.
   • combinaciones con repetición
     • En combinatoria, las combinaciones con repetición de un conjunto son las distintas formas en que se puede hacer una selección de elementos de un conjunto dado, permitiendo que las selecciones puedan repetirse. De manera formal, una combinación con repetición es la selección de un multiconjunto cuyos elementos pertenezcan a un conjunto dado.
       • Por ejemplo, {a, e, e, i, o, o, o, u} es el mismo multiconjunto que {e, i, o, u, a, e, o, o} Para ilustrar el problema, consideremos el conjunto X={a, b, c, d}. Listemos todos los posibles multiconjuntos de 3 elementos obtenidos del conjunto X. Para brevedad, indicaremos las letras como si fuesen una palabra: (aaa aab aac aad abb abc abd acc acd add bbb bbc bbd bcc bcd bdd ccc ccd cdd ddd). Se recalca que el orden no importa, por esto es que no se lista por ejemplo, aca ya que el multiconjunto {a, c, a} es el mismo que el multiconjunto {a, a, c}. Estas selecciones donde se permite repetición pero no se toma en cuenta el orden se denominan combinaciones con repetición.

4. Permutaciones

   • Permutación sin repetición
     • Permutaciones sin repetición o permutaciones ordinarias de n elementos (de orden n) son los distintos grupos de n elementos distintos que se pueden hacer, de forma que dos grupos se diferencian únicamente en el orden de colocación. Se representa por Pn. Para construir las permutaciones sin repetición de un conjunto de n elementos, tenemos que construir grupos de n elementos sin que se puedan repetir. Se trata entonces de hacer lo mismo que se ha hecho con las variaciones sin repetición de orden n a partir de un conjunto de n elementos.
   • Permutaciones circulares
     • Las permutaciones circulares son un caso particular de las permutaciones. Se utilizan cuando los elementos se han de ordenar "en círculo", (por ejemplo, los comensales en una mesa), de modo que el primer elemento que "se sitúe" en la muestra determina el principio y el final de muestra. {PC_n = P_{n-1} = (n-1)!}
   • Permutaciones con Repetición
     • Una permutación con repetición consiste en una permutación de m elementos, de los cuales hay varios que son iguales entre sí. Y por tanto, a la hora de calcular las distintas formas de ordenar los m elementos hay diferencias con respecto a si no hubiese elementos iguales.Por ejemplo, dado un conjunto A = {1, 2, 3} (n.º de elementos = m = 3), las permutaciones de los elementos de dicho conjunto son: 123, 132, 213, 231, 312 y 321. Se obtiene 6 ordenaciones distintas de los elementos y se verifica que n.º de permutaciones = 3! = 6.