7.2: Permutaciones y combinaciones
- Page ID
- 85286
- Analiza los conceptos básicos de combinaciones y permutaciones, y cómo calcular la probabilidad de ciertos eventos, como errores de n bits en una palabra clave.
El “juego” de lotería consiste en escoger
Responder a tales preguntas ocurre en muchas aplicaciones más allá de los juegos. En las comunicaciones digitales, por ejemplo, podría preguntarse cuántos posibles errores de doble bit pueden ocurrir en una palabra clave. Numerando las posiciones de bit de 1 a N, la respuesta es la misma que el problema de la lotería con k=6. Resolver este tipo de problemas equivale a comprender las permutaciones -la cantidad de formas de elegir las cosas cuando el orden importa como en las alineaciones de béisbol- y las combinaciones - la cantidad de formas de elegir las cosas cuando el orden no importa como en las loterías y errores de bits.
Calcular permutaciones es lo más fácil. Si vamos a elegir k números de un grupo de n, tenemos n opciones para el primero. Para la segunda opción, tenemos n-1. Por lo tanto, el número de secuencias ordenadas de longitud dos es n (n-1). Continuar eligiendo hasta que hagamos k elecciones significa que el número de permutaciones es
\[n(n-1)(n-2)...(n-k+1) \nonumber \]
Este resultado se puede escribir en términos de factoriales como
\[\frac{n!}{(n-k)!} \nonumber \]
con
\[n!=n(n-1)(n-2)...1 \nonumber \]
Por conveniencia matemática, definimos 0! =1.
Cuando el orden no importa, el número de combinaciones es igual al número de permutaciones dividido por el número de ordenamientos. El número de formas en que se puede ordenar un grupo de k cosas es igual a k! . Así, una vez que elegimos los nueve arrancadores para nuestro juego de béisbol, tenemos
\[9!=362,880 \nonumber \]
¡diferentes alineaciones! El símbolo para la combinación de k cosas extraídas de un charco de n es
\[\binom{n}{k} \nonumber \]
y es igual
\[\frac{n!}{(n-k)!k!} \nonumber \]
¿Cuáles son las posibilidades de ganar la lotería? Supongamos que eliges 6 números de los números 1-60.
Solución
\[\binom{60}{6}=\frac{60!}{54!6!}=50,063,860 \nonumber \]
Los combinatorios ocurren en lugares interesantes. Por ejemplo, Newton derivó que el n -ésimo poder de una suma obedeció a la fórmula
\[(x+y)^{n}=\binom{n}{0}x^{n}+\binom{n}{1}x^{n-1}y+\binom{n}{2}x^{n-2}y^{2}+...+\binom{n}{n}y^{n} \nonumber \]
¿Qué es igual la suma de los coeficientes binomiales? En otras palabras, ¿qué es
\[\sum_{k=0}^{n}\binom{n}{k} \nonumber \]
Solución
Debido al teorema binomial de Newton, la suma es igual
\[(1+1)^{n}=2^{n} \nonumber \]
Un problema relacionado es calcular la probabilidad de que dos bits cualesquiera estén en error en una longitud-
\[p^{2}(1-p)^{n-2} \nonumber \]
La probabilidad de que ocurra un error de dos bits en cualquier lugar es igual a esta probabilidad multiplicada por el número de combinaciones:
\[\binom{n}{2}p^{2}(1-p)^{n-2} \nonumber \]
Tenga en cuenta que la probabilidad de que se produzcan cero o uno o dos, etc., los errores deben ser uno; en otras palabras, ¡algo le debe pasar a la palabra clave! Eso significa que debemos tener
\[\binom{n}{0}(1-p)^{n}+\binom{n}{1}(1-p)^{n-1}+\binom{n}{2}p^{2}(1-p)^{n-2}+...+\binom{n}{n}p^{n}=1 \nonumber \]
¿Puedes probarlo?