Permutación vs. Combinación: ¿Cuál es la diferencia entre la fórmula de permutación y la fórmula de combinación?

Permutación vs. Combinación: ¿Cuál es la diferencia entre la fórmula de permutación y la fórmula de combinación?

Aquí está la versión corta.

Tomemos como ejemplo el toque de campanas en una iglesia.

Una permutación es un ordenamiento de las campanas. Estás averiguando el mejor orden para tocarlas.

Una combinación es la elección de las campanas. Estás eligiendo las campanas a tocar. Si tienes muchas campanas, primero las elegirías y luego pensarías en ordenarlas.

Esto da lugar a la identidad familiar: (n P r) = (n C r) * r!

La forma de ordenar r elementos de n es elegir primero r elementos de n, y luego ordenar los r elementos (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 fan del pensamiento de primeros principios. Para entender un problema, llegar al núcleo del mismo, y razonar a partir de ahí.

No hacer esto suele ser la fuente de la 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 simplemente recordarlo.

Como puedes imaginar, esto no es lo ideal. Así que, de vez en cuando, me permito un ejercicio de derivar cosas de la fuente, y construir la intuición de cómo funcionan las cosas.

Esta vez, estamos construyendo la intuición para las permutaciones y combinaciones.

Por ejemplo, ¿sabes 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?

Empecemos por el origen. Los factoriales, las permutaciones y las combinaciones nacieron de los matemáticos que jugaban juntos, al igual que Steve Jobs y Steve Wozniak fundaron Apple jugando juntos en su garaje.

Al igual que Apple se convirtió en una empresa rentable de pleno derecho, el simple factorial, !, se convirtió en el átomo de todo un campo de las matemáticas: la combinatoria.

Olvídate de todo, empecemos a pensar desde la base.

El primer caso de uso interesante que se conoce vino de las iglesias en el siglo XVII.

¿Te has preguntado cómo se tocan las campanas en las iglesias? Hay una máquina que las «toca» en orden. Se pasó a las máquinas porque las campanas son demasiado grandes. Además, hay montones de campanas.

¿Cómo se ha averiguado la mejor secuencia para tocarlas? ¿Y si querían cambiar las cosas? ¿Cómo podían encontrar el mejor sonido? Cada campanario tenía hasta 16 campanas.

No se podía cambiar la rapidez con la que se tocaba una campana: las máquinas sólo tocaban una campana cada segundo. Lo único que podías hacer era cambiar el orden de las campanas. Así que este reto consistía en averiguar el mejor orden.

¿Podríamos, por el camino, averiguar también todos los órdenes posibles? Queremos conocer todos los órdenes posibles para saber si vale la pena probarlos todos.

Un campanero, Fabian Stedman aceptó este reto.

Empezó con 2 campanas. ¿Cuáles son los diferentes ordenamientos en los que podría tocar estas campanas?

1 y 2.
o
2 y 1.

Esto tenía sentido. No había otra manera.

¿Qué tal con 3 campanas?

1, 2 y 3.
1, 3 y 2.

Entonces empezando con la segunda campana,

2, 1 y 3.
2, 3 y 1.

Entonces empezando con la tercera campana,

3, 1 y 2.
3, 2, y 1.

Total, 6.

Entonces se dio cuenta de que esto era muy parecido a dos campanas.

Si arreglaba la primera campana, entonces el número de maneras de ordenar las dos campanas restantes era siempre dos.

¿De cuántas maneras podía arreglar la primera campana? Cualquiera de las 3 campanas podría ser la elegida.

Bien, continuó. Entonces llegó a las 5 campanas.

Aquí es cuando se dio cuenta de que hacer las cosas a mano es inmanejable. Sólo tienes un tiempo en el día, tienes que tocar las campanas, no puedes estar atascado sacando todas las campanas posibles. ¿Había una manera de resolver esto rápidamente?

Volvió a su intuición.

Si tenía 5 campanas, y arreglaba la primera campana, todo lo que tenía que hacer era averiguar cómo ordenar 4 campanas.

¿Para 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 él sabía cómo hacer esto!

Entonces, ordenar 5 campanas = 5 * ordenar 4 campanas.

Ordenar 4 campanas = 4 * ordenar 3 campanas

Ordenar 3 campanas = 3 * ordenar 2 campanas.

.. Ves el patrón, ¿no?

Dato divertido: Esta es la clave de una técnica de programación llamada recursividad.

Él también lo hizo. Aunque le llevó mucho más tiempo, ya que nadie cercano a él lo había descubierto ya.

Así, averiguó que la ordenación de 5 campanas = 5 * 4 * 3 * 2 * 1.

Esta fórmula de ordenación, en 1808, pasó a conocerse como el factorial.

Pensamos en la notación factorial como la base, pero la idea existía mucho antes de que tuviera un nombre. No fue hasta que el matemático francés Christian Kramp se dio cuenta de que se utilizaba en algunos lugares que le dio el nombre de factorial.

Esta ordenación de campanas se llama permutación.

Una permutación es una ordenación de elementos.

Cuando se aprende algo, creo que ayuda a mirar las cosas desde todos los ángulos diferentes, para solidificar la comprensión.

¿Qué pasa si intentamos derivar la fórmula anterior directamente, sin tratar de reducir el problema a un número menor de campanas?
Tenemos 5 espacios, ¿verdad?

¿De cuántas maneras podemos elegir la primera campana? 5, porque ese es el número de campanas que tenemos.

¿La segunda campana? Bueno, hemos gastado una campana al colocarla en la primera posición, así que nos quedan 4 campanas.

¿La tercera campana? Bueno, hemos elegido las dos primeras, así que sólo quedan 3 campanas para elegir.

¿La cuarta campana? Sólo quedan 2 campanas, así que 2 opciones.
¿La quinta campana? Sólo queda 1, así que 1 opción.

Y ahí lo tenemos, el número total de ordenamientos es 5 * 4 * 3 * 2 * 1

Así, tenemos nuestra primera fórmula general.

El número de formas de pedir N artículos es N!

Ahora, nos enfrentamos a un problema diferente. El rey mandó hacer campanas nuevas para todas las iglesias. Algunas son bonitas, otras están bien, otras te dejarán sordo. Pero cada una es única. Cada una hace su propio sonido. Una campana ensordecedora rodeada de campanas bonitas puede sonar majestuosa.

Pero, en nuestro campanario todavía caben 5 campanas, así que tenemos que averiguar cuál es la mejor ordenación de las 8 campanas que hicieron los hábiles campaneros.

Usando la lógica anterior, podemos proceder.

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 * 4 posibles ordenaciones de 8 campanas en 5 espacios.

Si estás familiarizado con la versión de la fórmula de (n P r), que es n! / (n-r)!, no te preocupes, ¡también la derivaremos pronto!

Una mala manera 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 entender por qué funciona esta fórmula. Antes de llegar ahí, echemos un vistazo a la elección de cosas, o a la Combinación.

La Combinación

Ahora que sabemos cómo ordenar las cosas, ¡podemos averiguar cómo elegirlas!

Consideremos el mismo problema. Hay un campanario con 5 campanas, y tú tienes 8 campanas. Sin embargo, ahora mismo, no quieres averiguar el orden de las campanas (recuerda que eso es una permutación).

En su lugar, quieres elegir las 5 mejores campanas, y dejar que otra persona con mejor gusto musical decida el orden. En efecto, estamos dividiendo el problema en dos partes: Primero, averiguamos qué campanas elegir. A continuación, averiguamos cómo ordenar las campanas elegidas.

¿Cómo se eligen 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.

Ya que sabemos cómo ordenar las campanas, vamos a usar esta información para saber cómo elegir las campanas. ¿Suena imposible? Espera a ver las bonitas matemáticas que hay en juego.

Imaginemos que todas las campanas están en fila.

Antes de encontrar todas las formas de elegir las campanas, vamos a centrarnos en una forma de elegir campanas.

Una forma es elegir 5 cualquiera al azar. Esto no nos ayuda mucho a resolver el problema, así que vamos a probar otra forma.

Ponemos las campanas en fila, y elegimos las 5 primeras. Esta es una forma de elegir las campanas.

Nota que, aunque cambiemos de posición las 5 primeras campanas, la elección no cambia. Siguen siendo la misma forma de elegir 5 campanas únicas.

Esto es cierto para las tres últimas campanas también.

Ahora, el hermoso truco matemático – para esta única forma de elegir las 5 campanas, ¿cuáles son todas las ordenaciones de 8 campanas donde elegimos exactamente estas 5 campanas? De la imagen anterior, son todas las ordenaciones de las 5 campanas (5!) y todas las ordenaciones de las tres campanas restantes (3!).

Así, para cada forma de elegir 5 campanas, tenemos (5! * 3!) ordenaciones de 8 campanas.

¿Cuáles son las ordenaciones totales posibles de 8 campanas? 8!.

Recuerda que, para cada elección de las 5 primeras campanas, tenemos (5! * 3!) ordenaciones de 8 campanas que dan la misma elección.

Entonces, si multiplicamos el número de formas de elegir las 5 primeras campanas por todas las posibles ordenaciones de una elección, deberíamos obtener el número total de ordenaciones.

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!)

Hemos encontrado una explicación intuitiva de cómo elegir 5 cosas entre 8.

Ahora, podemos generalizar esto. Si tenemos N cosas, y queremos elegir R de ellas, significa que trazamos una línea en R.

Lo que significa que los elementos restantes serán N-R. Así, para una elección de R elementos, tenemos R! * (N-R)! ordenaciones que dan los mismos R elementos.

Para todas las formas de elegir R elementos, tenemos N! / (R! * (N-R)!) posibilidades.

El número de formas de elegir r elementos de n es (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 espolvoreada, volvamos a la Parte 2 de nuestro trabajo. Nuestro querido amigo eligió las mejores 5 campanas averiguando todas las combinaciones posibles de 5 campanas.

Ahora es nuestro trabajo encontrar la melodía perfecta averiguando el número de ordenamientos.

Pero, esta es la parte fácil. Ya sabemos cómo ordenar 5 elementos. Es 5!, y hemos terminado.

Así que, para permutar (ordenar) 5 elementos de 8, primero elegimos 5 elementos, y luego ordenamos los 5 elementos.

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 r elementos de n es (n P r) = n! / (n-r)!

Diferencia entre permutación y combinación

Espero que esto deje clara la diferencia entre permutaciones y combinaciones.

Las permutaciones son ordenaciones, mientras que las combinaciones son elecciones.

Para ordenar N elementos, encontramos dos formas intuitivas de averiguar la respuesta. Ambas conducen a la respuesta, N!.

Para permutar 5 de 8 elementos, primero hay que elegir los 5 elementos y luego ordenarlos. Se elige usando (8 C 5), luego se ordenan los 5 usando 5!.

Y la intuición para elegir R de N es averiguar todos los ordenamientos (N!) y dividir por los ordenamientos donde el primer R y el último N-R permanecen iguales (R! y (N-R)!).

Y, eso es todo lo que hay en las permutaciones y combinaciones.

Toda permutación y combinación avanzada utiliza esto como base. ¿Combinación con reemplazo? La misma idea. ¿Permutación con elementos idénticos? Misma idea, sólo cambia el número de ordenaciones, ya que algunos elementos son idénticos.

Si te interesa, podemos entrar en los casos complejos en otro ejemplo. Avísame en Twitter.

Consulta más posts en mi blog, y únete a la lista de correo semanal.

Notas finales

1. Así es como imagino que resolvió las cosas. No lo tomes como una lección de historia.
2. Los indios tenían, en el siglo XII, 400 años antes que él.