Aquí está la versión corta.
Tomemos como ejemplo el repicar de campanas en una iglesia.
Una permutación es un orden de las campanas. Estás averiguando el mejor orden para llamarlos.
Una combinación es la elección de campanas. Estás eligiendo las campanas para sonar. Si tiene demasiadas campanas, primero las elegiría y luego pensaría en ordenarlas.
Esto da lugar a la identidad familiar: (n P r) = (n C r) * r!
La forma de ordenar los rartículos nes elegir primero los rartículos ny luego ordenarlos r( r!)
Y esto significa (n P r) = n! / (n-r)!y(n C r) = n! / ( (n-r)! * r! )
¿Pero quieres saber cómo recordar esto para siempre?
Soy un gran admirador del pensamiento de los primeros principios. Para comprender un problema, vaya al meollo del mismo y razone desde allí.
No hacer esto suele ser una fuente de confusión: si no entiendo cómo funcionan las cosas, no sé dónde colgar los conceptos. Mi marco mental no está completo, así que decido recordarlo.
Como puede imaginar, esto no es ideal. Entonces, de vez en cuando, me entrego a un ejercicio de derivar cosas de la fuente y a desarrollar la intuición de cómo funcionan las cosas.
Esta vez, estamos construyendo intuición para permutaciones y combinaciones.
Por ejemplo, ¿sabe por qué la fórmula para una combinación es (n C r)? ¿De dónde viene esto? ¿Y por qué se utilizan aquí los factoriales?
Comencemos por la fuente. Factoriales, permutaciones y combinaciones nacieron de matemáticos jugando juntos, al igual que Steve Jobs y Steve Wozniak fundaron Apple tocando juntos en su garaje.
Así como Apple se convirtió en una empresa rentable en toda regla, el factorial simple se !convirtió en el átomo de todo un campo de las matemáticas: la combinatoria.
Olvídese de todo, empecemos a pensar de abajo hacia arriba.
El primer caso de uso interesante conocido provino de las iglesias en el siglo XVII.
¿Te has preguntado cómo suenan las campanas en las iglesias? Hay una máquina que los "hace sonar" en orden. Cambiamos a las máquinas porque las campanas son demasiado grandes. Además, hay toneladas de campanas.
¿Cómo descubrió la gente la mejor secuencia para llamarlos? ¿Y si quisieran cambiar las cosas? ¿Cómo podrían encontrar el mejor sonido? ¡Cada campanario tenía hasta 16 campanas!
No se podía cambiar la rapidez con la que se podía hacer sonar una campana: las máquinas solo sonaban una campana por segundo. Lo único que podía hacer era cambiar el orden de las campanas. Entonces, este desafío consistía en encontrar el mejor orden.
¿Podríamos, por el camino, averiguar también todos los pedidos posibles? Queremos conocer todos los pedidos posibles para averiguar si vale la pena probarlos todos.
Un campanero, Fabian Stedman asumió este desafío.
Comenzó con 2 campanas. ¿Cuáles son los diferentes ordenamientos en los que podría hacer sonar estas campanas? [1]
1 y 2.
o
2 y 1.
Esto tenía sentido. No había otra forma.
¿Qué tal con 3 campanas?
1, 2 y 3.
1, 3 y 2.
Luego, comenzando con la segunda campana,
2, 1 y 3.
2, 3 y 1.
Luego, comenzando con la tercera campana,
3, 1 y 2.
3, 2 y 1.
Total, 6.
¡Entonces se dio cuenta de que esto era muy similar a dos campanas!
Si arreglaba la primera campana, entonces el número de formas de ordenar las dos campanas restantes era siempre dos.
¿De cuántas formas podría arreglar la primera campana? ¡Cualquiera de las 3 campanas podría ser la única!
Está bien, continuó. Luego alcanzó las 5 campanas.
Fue entonces cuando se dio cuenta de que hacer las cosas a mano era complicado. Tienes poco tiempo en el día, tienes que tocar las campanas, no puedes quedarte atrapado sacando todas las campanas posibles. ¿Había alguna forma de resolver esto rápidamente?
Volvió a su intuición.
Si tenía 5 campanas y arregló la primera campana, todo lo que tenía que hacer era averiguar cómo pedir 4 campanas.
¿Por 4 campanas? Bueno, si tenía 4 campanas y arregló la primera campana, todo lo que tenía que hacer era averiguar cómo pedir 3 campanas.
¡Y sabía cómo hacer esto!
Por lo tanto, ordenar 5 campanas = 5 * ordenar 4 campanas.
Pedido de 4 campanas = 4 * pedido de 3 campanas
Pedido de 3 campanas = 3 * pedido de 2 campanas.
.. Ves el patrón, ¿no?
Dato curioso: esta es la clave de una técnica de programación llamada recursividad.
Él también lo hizo. Aunque, le tomó mucho más tiempo, ya que nadie cerca de él ya lo había descubierto. [2]
Por lo tanto, descubrió que el pedido de 5 campanas = 5 * 4 * 3 * 2 * 1.
Esta fórmula de ordenamiento, en 1808, se conoció como factorial.
Pensamos en la notación factorial como base, pero la idea existió mucho antes de que tuviera un nombre. Fue solo cuando el matemático francés Christian Kramp notó que se usaba en algunos lugares que lo llamó factorial.
Este orden de campanas se llama permutación.
Una permutación es un pedido de elementos.
Al aprender algo, creo que es útil mirar las cosas desde todos los ángulos diferentes, para solidificar la comprensión.
¿Qué pasa si intentáramos derivar la fórmula anterior directamente, sin intentar reducir el problema a un número menor de campanas?
Tenemos 5 espacios, ¿verdad?
¿De cuántas formas podemos elegir la primera campana? 5, porque ese es el número de campanas que tenemos.
¿La segunda campana? Bueno, usamos una campana cuando la colocamos en la primera posición, así que nos quedan 4 campanas.
¿La tercera campana? Bueno, hemos elegido los dos primeros, por lo que solo quedan 3 campanas para elegir.
¿La cuarta campana? Solo quedan 2 campanas, entonces 2 opciones.
¿La quinta campana? Solo queda 1, así que 1 opción.
Y ahí lo tenemos, el número total de pedidos es 5 * 4 * 3 * 2 * 1
Por tanto, tenemos nuestra primera fórmula general.
El número de formas de pedirNartículos es
N!
La permutación
Ahora nos enfrentamos a un problema diferente. El rey ordenó que se hicieran nuevas campanas para cada iglesia. Algunos son agradables, otros están bien, algunos te harán quedar sordo. Pero cada uno es único. Cada uno hace su propio sonido. Una campana ensordecedora rodeada de bonitas campanas puede sonar majestuosa.
Pero, nuestro campanario todavía tiene 5 campanas, por lo que debemos averiguar cuál es el mejor pedido de 8 campanas que hicieron los expertos fabricantes de campanas.
Usando la lógica anterior, podemos continuar.
Para la primera campana, podemos elegir cualquiera de las 8 campanas.
Para la segunda campana, podemos elegir cualquiera de las 7 campanas restantes ... y así sucesivamente.
Al final, obtenemos 8 * 7 * 6 * 5 * 4posibles pedidos de 8 campanas en 5 espacios.
Si está familiarizado con la versión de fórmula de (n P r), que es n! / (n-r)!, no se preocupe, ¡también la obtendremos pronto!
Una mala forma de derivarlo es multiplicar tanto el numerador como el denominador por 3. en nuestro ejemplo anterior -
obtenemos 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 / 3 * 2 * 1= 8! / 3!.
Pero esto no nos ayuda a comprender por qué funciona esta fórmula. Antes de llegar allí, echemos un vistazo a la elección de las cosas o la combinación.
La combinación
Ahora que sabemos cómo ordenar las cosas, ¡podemos descubrir cómo elegirlas!
Consideremos el mismo problema. Hay un campanario con 5 campanas y tú tienes 8 campanas. Sin embargo, en este momento, no desea averiguar el orden de las campanas (recuerde que eso es una permutación).
En su lugar, desea elegir las 5 mejores campanas y dejar que otra persona con mejor gusto musical descubra el pedido. De hecho, estamos dividiendo el problema en partes: primero, averiguamos qué campanas elegir. A continuación, descubrimos cómo ordenar las campanas elegidas.
¿Cómo eliges las campanas? Esta es la "combinación" de permutaciones y combinación.
La combinación es una selección. Estás siendo selectivo. Estás eligiendo 5 campanas de las 8 que han hecho tus artesanos.
Como sabemos cómo ordenar campanas, usaremos esta información para averiguar cómo elegir campanas. ¿Suena imposible? Espere hasta que vea las hermosas matemáticas involucradas.
Imaginemos que todas las campanas están en una línea.
Antes de encontrar todas las formas de elegir las campanas, centrémonos en una forma de elegir las campanas.
Una forma es elegir 5 al azar. Esto no nos ayuda mucho a resolver el problema, así que intentemos de otra manera.
Ponemos las campanas en una línea y elegimos las primeras 5. Esta es una forma de elegir las campanas.
Tenga en cuenta que, incluso si cambiamos las posiciones de las primeras 5 campanas, la elección no cambia. Siguen siendo la misma una forma de elegir 5 campanas únicas.
Esto también es cierto para las últimas tres campanas.
Ahora, el hermoso truco de matemáticas: para esta única forma de elegir las 5 campanas, ¿cuál es el orden de las 8 campanas donde elegimos exactamente estas 5 campanas? De la imagen de arriba, son todos los ordenamientos de las 5 campanas ( 5!) y todos los ordenamientos de las tres campanas restantes ( 3!).
Por lo tanto, para cada forma de elegir 5 campanas, tenemos ( 5! * 3!) órdenes de 8 campanas.
¿Cuáles son los posibles ordenamientos totales de 8 campanas? 8!.
Recuerde, para cada elección de las primeras 5 campanas, tenemos ( 5! * 3!) ordenaciones de 8 campanas que dan la misma opción.
Entonces, si multiplicamos el número de formas de elegir las primeras 5 campanas con todos los posibles ordenamientos de una opción, deberíamos obtener el número total de ordenamientos.
Ways to choose 5 bells * orderings of one choice = Total orderings Entonces,
Ways to choose 5 bells = the total possible orderings / total orderings of one choice. En matemáticas, eso se convierte en:
(8 C 5) = 8! / ( 5! * 3!) He aquí, hemos encontrado una explicación intuitiva de cómo elegir 5 cosas de 8.
Ahora, podemos generalizar esto. Si tenemos N cosas y queremos elegir R de ellas, significa que dibujamos una línea en R.
Lo que significa que los elementos restantes serán N-R. Entonces, para una selección de Rartículos, tenemos R! * (N-R)!pedidos que dan los mismos Rartículos.
Para todas las formas de elegir Rartículos, tenemos N! / (R! * (N-R)!)posibilidades.
La cantidad de formas de elegir relementos nes(n C r) = n! / (r! * (n-r)!)
En términos coloquiales, (n C r) también se pronuncia n choose r, lo que ayuda a solidificar la idea de que las combinaciones son para elegir elementos.
La Permutación - revisitada
Con la combinación hecha y desempolvada, volvamos a la Parte 2 de nuestro trabajo. Nuestro querido amigo eligió las mejores 5 campanas al descubrir todas las combinaciones posibles de 5 campanas.
Ahora es nuestro trabajo encontrar la melodía perfecta calculando el número de pedidos.
Pero esta es la parte fácil. Ya sabemos cómo pedir 5 artículos. Está 5!, y hemos terminado.
Entonces, para permutar (ordenar) 5 artículos de 8, primero elegimos 5 artículos, luego ordenamos los 5 artículos.
En otras palabras,
(8 P 5) = (8 C 5) * 5! Y si ampliamos la fórmula, (8 P 5) = (8! / ( 5! * 3!)) * 5!
(8 P 5) = 8! / 3!.
Y hemos cerrado el círculo a nuestra fórmula original, derivada correctamente.
El número de formas de ordenar rartículos nes(n P r) = n! / (n-r)!
Diferencia entre permutación y combinación
Espero que esto haga que la diferencia entre permutaciones y combinaciones sea muy clara.
Las permutaciones son ordenaciones, mientras que las combinaciones son opciones.
Para ordenar N elementos, encontramos dos formas intuitivas de averiguar la respuesta. Ambos conducen a la respuesta N!.
Para permutar 5 de 8 elementos, primero debe elegir los 5 elementos y luego ordenarlos. Usted elige usar (8 C 5), luego ordena los 5 usando 5!.
Y la intuición para la elección Rde Nes averiguar todos los ordenamientos ( N!) y dividiendo por ordenamientos donde el primer Ry último N-Rsiguen siendo los mismos ( R!y (N-R)!).
Y eso es todo lo que hay en las permutaciones y combinaciones.
Cada permutación y combinación avanzada usa esto como base. ¿Combinación con reemplazo? La misma idea. ¿Permutación con elementos idénticos? Misma idea, solo cambia el número de pedidos, ya que algunos artículos son idénticos.
Si está interesado, podemos analizar los casos complejos en otro ejemplo. Házmelo saber en Twitter.
Vea más publicaciones en mi blog y únase a la lista de correo semanal.Notas finales
- Así es como me imagino que descubrió las cosas. No lo tome como una lección de historia.
- Los indios tenían, en el siglo XII, 400 años antes que él.