Cómo entender permutaciones y combinaciones.

Aquí hay un par de ejemplos. Primero, cualquiera que lea esto debe saber que una permutación se refiere a un arreglo (es decir, el orden importa), y una combinación se refiere a elegir un grupo de elementos (es decir, el orden no importa).

1) Eres un juez en un concurso de belleza para gatos. Hay 50 gatos, y debes elegir el más bonito, el segundo más bonito y el tercero más bonito. (Nuestro dulce gato, Persia, no está disponible, porque no sería justo). ¿De cuántas maneras puedes hacer esto?

RESPUESTA: Tenga en cuenta que el orden importa aquí, por lo que este es un problema de permutación. Hay 50 formas de elegir el gato más bonito, 49 formas de elegir el segundo más bonito y 48 formas de elegir el tercero más bonito. Así que hay 50 ∗ 49 ∗ 48 formas de escoger estos gatos. En general, la cantidad de formas de permutar (ordenar) r elementos de un conjunto de n elementos es [math] \ frac {n!} {(Nr)!} [/ Math].

2) Desea comprar 3 gatos en una tienda de mascotas que tiene 50 gatos. ¿De cuántas maneras puedes hacer esto? RESPUESTA: Tenga en cuenta que el orden no importa aquí, por lo que este es un problema de combinación. (Matemáticamente, estamos preguntando cuántos subconjuntos de tamaño 3 hay de un conjunto de tamaño 50). Una forma de responder esto es pensarlo primero como si el orden importara. Es probable que hagas esto de todos modos eligiendo tu primer gato, tu segundo gato y tu tercer gato. Entonces obtendría la misma respuesta que la anterior: 50 ∗ 49 ∗ 48. Pero podrías haber elegido estos gatos en cualquier orden. Por lo tanto, debe dividir este resultado por la cantidad de formas en que estos 3 gatos pueden ordenar. Y eso es 3 ∗ 2 ∗ 1. Entonces, su respuesta final es 50 ∗ 49 ∗ 483 ∗ 2 ∗ 1. En general, la cantidad de formas de elegir r ítems de un conjunto de n ítems es [matemática] \ frac {n!} {(Nr)! R!} [/matemáticas]. Esto se llama coeficiente binomial y generalmente se escribe como [math] \ binom {n} {r} [/ math].

Lo que hago es usar el lenguaje Python junto con las funciones en los itertools y los módulos sympy . Al escribir una secuencia de comandos rápida utilizando rutinas en estos módulos para calcular combinaciones, permutaciones, productos cartesianos, permutaciones y combinaciones en varios conjuntos, etc. y mostrando los conjuntos de resultados producidos, puedo refinar mi comprensión de lo que se requiere en una situación dada. Por ejemplo, aquí hay un script que genera todas las formas de colocar objetos [matemáticos] k [/ matemáticos] (distintos) en lugares [matemáticos] n [/ matemáticos]. Los lugares están numerados del 0 al 4, los objetos del 0 al 2. El script continúa generando cada combinación de 3 lugares del 4 y luego permutando los objetos dentro de esos lugares.

de itertools importa combinaciones, permutaciones

n = 5 ## número de lugares
k = 3 ## número de objetos para colocar

para una combinación en combinaciones (rango (n), k):
print (‘combinación:’, aCombination)
Para una permutación en permutaciones (rango (k)):
print (‘\ t’, aPermutation)

No he necesitado usar ninguna rutina simulada esta vez. Si no conoce Python, no se preocupe, probablemente le resulte fácil de aprender.

Descargo de responsabilidad: mi respuesta no es un sustituto de la iluminación que solo un buen libro de álgebra de secundaria podría proporcionar. Si eso es posible, te sugiero que dejes de leer mi respuesta un poco más y tomes un libro.

Todos los problemas de permutación y combinación le piden que calcule el número de arreglos o el número de opciones para un subconjunto que contiene elementos r de un conjunto que contiene n elementos, posiblemente bajo ciertas restricciones. La idea es dividir cada problema en subproblemas, que son arreglos más simples u opciones.

Me gusta la palabra plétora (también, tiene la ventaja de que todas sus letras son distintas, lo que simplifica la instrucción) . Comencemos con eso, ¿de acuerdo? Si tuviera que preguntarte, ¿cuántas palabras de dos letras puedes formar con las letras sacadas de la palabra plétora , cómo lo harías?

Hay exactamente 8 letras distintas en plétora. Existen estos dos lugares para llenar: __ __.

Elija una letra para el primer lugar (más a la izquierda). Puede elegir cualquiera de esas 8 letras, por lo que puede hacerlo de 8 maneras. Supongamos además que ya sabemos que eligió ‘p’ para el primer lugar. Puede elegir 7 de la letra restante (de ‘lethora’). Esas son 7 opciones si su primera letra es ‘p’. Dado que no hay nada inherentemente especial sobre ‘p’ que no pueda aplicarse al caso de cualquiera de las 8 letras posibles para el primer lugar, eso es {[matemáticas] 7 + 7 + 7 + … .. [/ matemáticas] ([ matemáticas] 8 [/ matemáticas] veces) [matemáticas] = 8 \ veces 7 [/ matemáticas]} formas en que puede organizar 8 letras distintas en 2 lugares.

De manera similar, para tres lugares diferentes, eso es [matemáticas] = 8 \ veces 7 \ veces 6 [/ matemáticas] arreglos posibles, para cuatro lugares, eso es [matemáticas] = 8 \ veces 7 \ veces 6 \ veces 5 [ /matemáticas]. En general, eso es [matemática] 8 \ veces 7 \ veces 6 \ veces … \ veces (8 – r + 1) [/ matemáticas] veces para r lugares con [matemáticas] 0 n cosas distintas en r lugares, y tiene la fórmula

número de arreglos = [matemáticas] \ frac {n!} {(n – r)!} [/ matemáticas]

Tenga en cuenta que esto también explica una pregunta frecuente sobre Quora; a saber, ¿cuál es la razón por la que tomamos 0! ser 1? Definimos 0! = 1 para que la fórmula anterior permanezca consistente para el caso r = n.

Vamos a entender lo que acabamos de hacer desde otro ángulo. Necesitamos organizar r cosas de n en r lugares diferentes. Entonces, primero elegimos r cosas de n, luego, para cada elección que hacemos, calculamos el número de formas posibles de organizarlas en r lugares. Denotamos la cantidad de formas en que podemos elegir r cosas de n [matemáticas] (r \ leq n) [/ matemáticas] como [matemáticas] ^ nC_r [/ matemáticas]. Para cada elección que hagamos, podemos tener [math] \ frac {r!} {(R – r)!} = R! [/ Math] arreglos distintos. Entonces, tenemos arreglos [math] ^ nC_rr! [/ Math] en total. Esto es solo [matemáticas] \ frac {n!} {(N – r)!} [/ Matemáticas], y así, tenemos la segunda fórmula fundamental:

[matemáticas] ^ nC_r = \ frac {n!} {r! (n – r)!} [/ matemáticas]

Para concluir, hagamos un ejemplo para ilustrar cómo dividimos un problema complejo en problemas más simples, resolvemos los problemas más simples y los combinamos para resolver un problema más complicado.

Problema: una escuela tiene 25 estudiantes en el quinto grado, 30 estudiantes en el sexto grado y 28 estudiantes en el séptimo grado. Necesitamos formar un equipo de fútbol compuesto por 5 estudiantes de 5to grado y 3 estudiantes de 6to y 7mo grado cada uno. Además, tenemos 11 camisetas numeradas del 1 al 11 y debemos asignar una camiseta a cada jugador del equipo. ¿De cuántas maneras podemos hacer esto?

Solución: Los subproblemas son los siguientes:

1. Número de formas de elegir 5 estudiantes de los 25 en el quinto grado ([matemáticas] ^ {25} C_5 [/ matemáticas]).
2. Número de formas de elegir 3 estudiantes de los 30 en sexto grado ([matemáticas] ^ {30} C_3 [/ matemáticas]).
3. Número de formas de elegir 3 estudiantes de los 28 en sexto grado ([matemáticas] ^ {28} C_3 [/ matemáticas]).
4. Número de formas de asignar 11 jugadores a 11 camisetas ([matemáticas] 11! [/ Matemáticas]).

Como era de esperar, la solución es [matemáticas] {^ {25} C_5} \ veces {^ {30} C_3} \ veces {^ {28} C_3} \ veces 11! [/ Matemáticas]. Te dejo para que descubras por qué.

Según mi experiencia, las permutaciones y combinaciones aparecen a menudo con la programación dinámica. La razón es que la cantidad de formas para que ocurra un evento es usualmente derivable al reducir una variable.

Primero, aprenda sobre la recursión claramente. Luego, observe cómo la programación dinámica almacena los valores anteriores y calcula el siguiente.

La próxima vez que vea este problema, defina B (n, k) en términos de B (n-1, k-1) o B (n, k-1). Pronto encontrarás un patrón.

La práctica y la paciencia son las claves para comprender las permutaciones y las combinaciones. La orientación adecuada también ayudará. P & C es un tema lógico en el que debe rascarse la cabeza y ser paciente. No hay reglas concretas y el enfoque para los diferentes problemas es diferente. P&C ayuda mucho en áreas como la programación competitiva. Preparé este tema del libro Arihant Algebra.