Permutaciones y combinaciones, las diversas formas en que los objetos de un conjunto pueden seleccionarse, generalmente sin reemplazo, para formar subconjuntos. Esta selección de subconjuntos se denomina permutación cuando el orden de selección es un factor, una combinación cuando el orden no es un factor. Al considerar la relación entre el número de subconjuntos deseados y el número de todos los subconjuntos posibles para muchos juegos de azar en el siglo XVII, los matemáticos franceses Blaise Pascal y Pierre de Fermat dieron impulso al desarrollo de la teoría combinatoria y de probabilidad.
combinatoria: coeficientes binomiales
n objetos se llama permutación de n cosas tomadas r a la vez. El número de permutaciones es
Los conceptos y las diferencias entre permutaciones y combinaciones se pueden ilustrar examinando todas las diferentes formas en que se puede seleccionar un par de objetos entre cinco objetos distinguibles, como las letras A, B, C, D y E. Si ambos se consideran las letras seleccionadas y el orden de selección, entonces son posibles los siguientes 20 resultados:
Cada una de estas 20 selecciones posibles diferentes se llama permutación. En particular, se denominan permutaciones de cinco objetos tomados de dos en dos, y el número de tales permutaciones posibles se denota con el símbolo 5 P 2, lea "5 permute 2". En general, si hay n objetos disponibles para seleccionar, y las permutaciones (P) se forman utilizando k de los objetos a la vez, el número de permutaciones posibles se denota con el símbolo n P k. Una fórmula para su evaluación es n P k = n! / (N - k)! La expresión n! —Leer “n factorial” - indica que todos los enteros positivos consecutivos desde 1 hasta e incluyendo n deben multiplicarse juntos, y 0! se define como igual a 1. Por ejemplo, usando esta fórmula, el número de permutaciones de cinco objetos tomados de dos en dos es
(Para k = n, n P k = n! Por lo tanto, para 5 objetos hay 5! = 120 arreglos).
Para combinaciones, se seleccionan k objetos de un conjunto de n objetos para producir subconjuntos sin ordenarlos. Al contrastar el ejemplo de permutación anterior con la combinación correspondiente, los subconjuntos AB y BA ya no son selecciones distintas; Al eliminar tales casos, solo quedan 10 subconjuntos posibles diferentes: AB, AC, AD, AE, BC, BD, BE, CD, CE y DE.
El número de tales subconjuntos se denota por n C k, lea "n elegir k". Para combinaciones, ya que k objetos tienen k! arreglos, hay k! permutaciones indistinguibles para cada elección de k objetos; por lo tanto, dividiendo la fórmula de permutación por k! produce la siguiente fórmula de combinación:
Esto es lo mismo que el coeficiente binomial (n, k) (ver teorema binomial). Por ejemplo, el número de combinaciones de cinco objetos tomados de dos en dos es
Las fórmulas para n P k y n C k se llaman fórmulas de conteo, ya que pueden usarse para contar el número de posibles permutaciones o combinaciones en una situación dada sin tener que enumerarlas todas.
