1.3: Combinaciones y permutaciones
- Page ID
- 117120
Pasamos primero a contar. Si bien esto suena simple, quizás demasiado sencillo de estudiar, no lo es. Cuando hablamos de contar, es una taquigrafía para determinar el tamaño de un conjunto, o más a menudo, los tamaños de muchos conjuntos, todos con algo en común, pero diferentes tamaños dependiendo de uno o más parámetros. Por ejemplo: ¿cuántos resultados son posibles cuando se enrolla una matriz? ¿Dos dados? \(n \)dados? Como se dijo, esto es ambiguo: ¿qué queremos decir con “resultado”? Supongamos que tiramos dos dados, digamos un dado rojo y un dado verde. ¿Es “rojo dos, verde tres” un resultado diferente al “rojo tres, verde dos”? En caso afirmativo, estamos contando el número de posibles resultados “físicos”, a saber 36. En caso negativo, hay 21. Incluso podríamos estar interesados simplemente en los posibles totales, en cuyo caso hay 11 resultados.
Incluso la primera interpretación bastante simple se basa en cierto grado de conocimiento sobre el conteo; primero hacemos explícitos dos hechos simples. En cuanto a los tamaños de conjunto, supongamos que sabemos que el conjunto\(A \) tiene tamaño\(m \) y el conjunto\(B \) tiene tamaño\(n\). ¿Cuál es el tamaño de\(A \) y\(B \) juntos, es decir, el tamaño de\(A\cup B\)? Si lo sabemos\(A \) y no\(B \) tenemos elementos en común, entonces el tamaño\(A\cup B \) es\(m+n\); si tienen elementos en común, necesitamos más información. Un problema sencillo pero típico de este tipo: si tiramos dos dados, ¿cuántas formas hay de conseguir ya sea 7 u 11? Ya que hay 6 formas de obtener 7 y dos formas de obtener 11, la respuesta es\(6+2=8\). Aunque este principio es sencillo, es fácil olvidar el requisito de que los dos conjuntos sean disjuntos, y de ahí usarlo cuando las circunstancias son de otra manera. A este principio se le suele llamar el principio de adición.
Este principio puede generalizarse: si los conjuntos\(A_1 \) a través\(A_n \) son disjuntos por pares y tienen tamaños\(m_1,\ldots m_n\), entonces el tamaño de\(A_1\cup\cdots\cup A_n=\sum_{i=1}^n m_i\). Esto se puede probar con un simple argumento de inducción.
¿Por qué sabemos, sin enumerarlos todos, que hay 36 resultados cuando se lanzan dos dados? Podemos ver los resultados como dos resultados separados, es decir, el resultado del troquel rodante número uno y el resultado del troquel rodante número dos. Para cada uno de los 6 resultados para el primer dado el segundo dado puede tener cualquiera de los 6 resultados, por lo que el total es\(6+6+6+6+6+6=36\), o de manera más compacta,\(6\cdot6=36\). Tenga en cuenta que realmente estamos usando el principio de adición aquí: set\(A_1 \) is all pairs\((1,x)\), set\(A_2 \) is all pairs\((2,x)\), y así sucesivamente. Esto es algo más sutil de lo que primero es aparente. En este sencillo ejemplo, los resultados del dado número dos no tienen nada que ver con los resultados del dado número uno. Aquí hay un ejemplo un poco más complicado: ¿cuántas formas hay de tirar dos dados para que los dos dados no coincidan? Es decir, descartamos 1-1, 2-2, y así sucesivamente. Aquí para cada valor posible en el dado número uno, hay cinco valores posibles para el dado número dos, pero son cinco valores diferentes para cada valor en el dado número uno. Aún así, porque todos son iguales, el resultado es\(5+5+5+5+5+5=30\), o\(6\cdot 5=30\). En general, entonces, si hay\(m \) posibilidades para un evento, y\(n \) para un segundo evento, el número de posibles resultados para ambos eventos juntos es\(m\cdot n\). A esto se le suele llamar el principio de multiplicación.
En general, si los\(n \) eventos tienen\(m_i \) posibles resultados, para\(i=1,\ldots,n\), donde cada uno no\(m_i \) se ve afectado por los resultados de otros eventos, entonces el número de posibles resultados en general es\(\prod_{i=1}^n m_i\). Esto también se puede probar por inducción.
Ejemplo \(\PageIndex{1}\)
¿Cuántos resultados son posibles cuando se lanzan tres dados, si no hay dos de ellos iguales? Los dos primeros dados juntos tienen\(6\cdot 5=30 \) posibles resultados, desde arriba. Para cada uno de estos 30 resultados, hay cuatro posibles resultados para el tercer dado, por lo que el número total de resultados es\(30\cdot 4=6\cdot 5\cdot 4=120\). (Tenga en cuenta que consideramos que los dados son distinguibles, es decir, una tirada de 6, 4, 1 es diferente a 4, 6, 1, porque el primer y segundo dado son diferentes en los dos tirados, aunque los números como conjunto son los mismos).
Ejemplo\(\PageIndex{2}\)
Supongamos que los bloques numerados del 1 a través\(n \) están en un barril;\(k \) los sacamos, colocándolos en una línea como lo hacemos nosotros. ¿Cuántos resultados son posibles? Es decir, ¿cuántos arreglos diferentes de\(k \) bloques podríamos ver?
Esto es esencialmente lo mismo que el ejemplo anterior: hay\(k \) “spots” para ser llenados por bloques. Cualquiera de los\(n \) bloques podría aparecer primero en la línea; luego cualquiera de los restantes\(n-1 \) podría aparecer a continuación, y así sucesivamente. El número de resultados es así\(n(n-1)(n-2)\cdots(n-k+1)\), por el principio de multiplicación. En el ejemplo anterior, el primer “spot” fue el die número uno, el segundo spot fue el die número dos, el tercer spot muere el número tres, y\(6\cdot5\cdot4=6(6-1)(6-2)\); fíjese en eso\(6-2=6-3+1\).
Este es un problema bastante general:
Definición\(\PageIndex{1}\): Permutations
El número de permutaciones de\(n \) cosas tomadas\(k \) a la vez es
\[(P(n,k)=n(n-1)(n-2)\cdots(n-k+1)={n!\over (n-k)!}.\nonumber \]
Una permutación de algunos objetos es un orden lineal particular de los objetos;\(P(n,k) \) en efecto cuenta dos cosas simultáneamente: el número de formas de elegir y\(k \) ordenar de\(n \) los objetos. Un caso especial útil es\(k=n\), en el que simplemente estamos contando el número de formas de ordenar todos los\(n \) objetos. Esto es\(n(n-1)\cdots(n-n+1)=n!\). Obsérvese que la segunda forma de\(P(n,k) \) a partir de la definición da\[\frac{n!}{(n-n)!}=\frac{n!}{0!}.\nonumber\] Esto es correcto sólo si\(0!=1\), así adoptamos la convención estándar que esto es cierto, es decir, definimos\(0! \) ser\(1\).
Supongamos que queremos contar solo el número de formas de elegir\(k \) artículos\(n\), es decir, no nos importa el pedido. En Ejemplo\(\PageIndex{1}\), contamos el número de tiradas de tres dados con diferentes números mostrando. Los dados eran distinguibles, o en un orden particular: un primer dado, un segundo y un tercero. Ahora queremos contar simplemente cuántas combinaciones de números hay, con 6, 4, 1 contando ahora como la misma combinación que 4, 6, 1.
Ejemplo\(\PageIndex{3}\)
Supongamos que íbamos a enumerar todas las 120 posibilidades en Ejemplo\(\PageIndex{1}\). La lista contendría muchos resultados que ahora deseamos contar como resultado único; 6, 4, 1 y 4, 6, 1 estarían en la lista, pero no deberían contarse por separado. ¿Cuántas veces aparecerá un solo resultado en la lista? Esto es un problema de permutación: hay\(3! \) órdenes en las que pueden aparecer 1, 4, 6, y los 6 estarán en la lista. De hecho cada resultado aparecerá en la lista 6 veces, ya que cada resultado puede aparecer en\(3! \) órdenes. De ahí que la lista sea demasiado grande por un factor de 6; el recuento correcto para el nuevo problema es\(120/6=20\).
Siguiendo el mismo razonamiento en general, si tenemos\(n \) objetos, el número de formas de elegir\(k \) de ellos es\(P(n,k)/k!\), ya que cada colección de\(k \) objetos será contabilizada por\(k! \) tiempos\(P(n,k)\).
Definición\(\PageIndex{2}\): Permutations
El número de subconjuntos de tamaño\(k \) de un conjunto de tamaños\(n \) (también llamado un\(n\) -set) es\[C(n,k)=\frac{P(n,k)}{k!}=\frac{n!}{k!(n-k)!}={n\choose k}.\nonumber\] La notación\(C(n,k) \) rara vez se usa; en cambio usamos\(n\choose k\), pronunciado "\(n \)elegir\(k\)”.
Ejemplo \(\PageIndex{4}\)
Considerar\(n=0,1,2,3\). Es fácil enumerar los subconjuntos de un pequeño\(n\) -set; un\(n\) -set típico es\(\{a_1,a_2,\ldots,a_n\}\). Un\(0\) -set, es decir, el conjunto vacío, tiene un subconjunto, el conjunto vacío; un\(1\) -set tiene dos subconjuntos, el conjunto vacío y\(\{a_1\}\); un\(2\) -subconjunto tiene cuatro subconjuntos\(\emptyset\),,\(\{a_1\}\),\(\{a_2\}\),\(\{a_1,a_2\}\); y un\(3\) -subconjunto tiene ocho:\(\emptyset\),\(\{a_1\}\),\(\{a_2\}\), \(\{a_3\}\),\(\{a_1,a_2\}\),\(\{a_1,a_3\}\),\(\{a_2,a_3\}\),\(\{a_1,a_2,a_3\}\). A partir de estas listas es entonces fácil de calcular\(n\choose k\):
\[\displaylines{\cr \matrix{ &\rlap{\lower 3pt\hbox{$\Rule{65pt}{0pt}{0.5pt}$}}\cr &0\cr n&1\cr &2\cr &3\cr }\left\vert \matrix{ 0&\lower 3.5pt\hbox{}\rlap{\smash{\raise 1.5em \hbox{$k$}}}1&2&3\cr 1\cr 1&1\cr 1&2&1\cr 1&3&3&1\cr }\right.\cr}\nonumber\]
Probablemente reconozcas estos números: este es el comienzo del Triángulo de Pascal. Cada entrada en el triángulo de Pascal se genera sumando dos entradas de la fila anterior: la que está directamente arriba, y la de arriba y a la izquierda. Esto sugiere que\({n\choose k}={n-1\choose k-1}+{n-1\choose k}\), y de hecho esto es cierto. Para que esto funcione pulcramente, adoptamos la convención de que\({n\choose k}=0 \) cuando\(k< 0 \) o\(k>n\).
Teorema \(\PageIndex{1}\)
\({n\choose k}={n-1\choose k-1}+{n-1\choose k}\).
- Prueba
-
Un\(n\) -set típico es\(A=\{a_1,\ldots,a_n\}\). Consideramos dos tipos de subconjuntos: los que contienen\(a_n \) y los que no. Si un\(k\) -subconjunto de\(A \) no contiene\(a_n\), entonces es un\(k\) -subconjunto de\(\{a_1,…,a_{n-1}\}\), y hay\(n-1\choose k \) de estos. Si sí contiene\(a_n\), entonces consiste en\(a_n \) y\(k-1 \) elementos de\(\{a_1,…,a_{n-1}\}\); ya que hay\(n-1\choose k-1 \) de estos, hay\(n-1\choose k-1 \) subconjuntos de este tipo. Así el número total de\(k\) -subconjuntos de\(A \) es\({n-1\choose k-1}+{n-1\choose k}\).
Tenga en cuenta que cuándo\(k=0\)\({n-1\choose k-1}={n-1\choose -1}=0\),, y cuándo\(k=n\)\({n-1\choose k}={n-1\choose n}=0\),, para que\({n\choose 0}={n-1\choose 0} \) y\({n\choose n}={n-1\choose n-1}\). Estos valores son los límites en el Triángulo de Pascal.
Muchos problemas de conteo se basan en el tipo de razonamiento que hemos visto. Aquí hay algunas variaciones sobre el tema.
Ejemplo\(\PageIndex{5}\)
Seis personas deben sentarse en una mesa redonda; ¿cuántos arreglos hay?
Solución
No está claro exactamente a qué nos referimos contar aquí. Si hay un “asiento especial”, por ejemplo, puede importar quién termine en ese asiento. Si esto no importa, solo nos importa la posición relativa de cada persona. Entonces puede o no importar si cierta persona está a la izquierda o a la derecha de otra. Entonces esta pregunta se puede interpretar de (al menos) tres formas. Vamos a responderles a todos.
Primero, si las sillas reales ocupadas por las personas importan, entonces esto es exactamente lo mismo que alinear a seis personas seguidas: 6 opciones para el asiento número uno, 5 para el asiento dos, y así sucesivamente, para un total de\(6!\). Si las sillas no importan, entonces\(6! \) cuenta el mismo arreglo demasiadas veces, una vez por cada persona que pueda estar en el asiento uno. Entonces el total en este caso lo es\(6!/6=5!\). Otro enfoque para esto: como los escaños reales no importan, sólo hay que poner a una de las seis personas en una silla. Entonces tenemos que arreglar las 5 personas restantes seguidas, lo cual se puede hacer de\(5! \) maneras. Por último, supongamos que lo único que nos importa es quién está al lado de quién, ignorando a derecha e izquierda. Entonces la respuesta anterior cuenta cada arreglo dos veces, una para el orden antihorario y otra para el sentido horario. Entonces el total es\(5!/2=P(5,3)\).
Hemos visto dos veces un principio general en funcionamiento: si podemos sobrecontar el conjunto deseado de tal manera que cada ítem se cuente el mismo número de veces, podemos obtener el conteo deseado simplemente dividiendo por el factor de sobrecento común. Esta seguirá siendo una idea útil. Una variación de este tema es sobrecontar y luego restar la cantidad de sobrecentos.
Ejemplo\(\PageIndex{6}\)
¿Cuántas formas hay de alinear a seis personas para que un par particular de personas no sean adyacentes?
Solución
Denotar a la gente\(A \) y\(B\). El número total de pedidos es\(6!\), pero esto cuenta esos pedidos con\(A \) y al\(B \) lado del otro. ¿Cuántos de estos hay? Piensa en estas dos personas como una unidad; ¿cuántas formas hay de alinear la\(AB \) unidad con las otras 4 personas? Tenemos 5 ítems, entonces la respuesta es\(5!\). Cada uno de estos órdenes corresponde a dos órdenes diferentes en las que\(A \) y\(B \) son adyacentes, dependiendo de si\(A \) o\(B \) es primero. Entonces el\(6! \) conteo es demasiado alto por\(2\cdot5! \) y el conteo que buscamos es\(6!-2\cdot 5!=4\cdot5!\).