Thread by @juliomulero

Si hay una pregunta clave en combinatoria es ¿cuántos/as…? La combinatoria trata de contar el número de configuraciones distintas que se pueden formar con los elementos de un conjunto. Así, criterios como el orden y la posibilidad de repetición son cruciales.

Dentro hilo ⬇️⬇️

Por ejemplo, dado un conjunto de siete letras distintas...

¿De cuántas formas se pueden ordenar? ¿Cuántas palabras de cuatro letras se pueden formar (tengan o no sentido)? ¿De cuántas formas se pueden escoger tres de ellas?

A fin de encontrar respuestas, debemos prestar atención a:

a) Los elementos de que disponemos.
b) Los elementos que debe contener cada grupo.
c) La posibilidad (o no) de repetir elementos.
d) La importancia o indiferencia en cuanto al orden en que aparecen los elementos.

Entre otros principios básicos, el principio general de recuento está muy presente en todo lo que sigue (aunque no lo explicitaré).

Si dos experimentos pueden realizarse de n y m formas diferentes, entonces los dos experimentos juntos se pueden realizar de n×m formas diferentes.

Un ejemplo bien sencillo es el siguiente:

Si tienes 3 camisetas y 2 pantalones de deporte, podrás combinarlas de 3×2 = 6 formas distintas.

Antes de comenzar, conviene recordar una función matemática muy chula: el #factorial.

Dado un número natural n, el factorial de n, que se denota como n! (¡grítalo, si es necesario!), viene dado por n×(n-1)×(n-2)×…×2×1. Por ejemplo, 5!=5×4×3×2×1.

Además, por definición, 0!=1.

Pues bien, en combinatoria suelen aparecer permutaciones, variaciones y combinaciones, dependiendo de si importa el orden de aparición de los elementos, si utilizamos todos (o una parte de) los elementos del conjunto inicial y/o si hay elementos repetidos en el conjunto inicial.

A continuación, mostraremos qué son las permutaciones, variaciones y combinaciones, y supondremos siempre que los elementos del conjunto inicial son distintos dos a dos, es decir, no hay repeticiones.

El caso en que hay repeticiones lo dejaremos para más adelante.

Permutaciones sin repetición

Llamamos #permutaciones sin repetición de n elementos distintos a cada uno de los distintos grupos que pueden formarse de manera que:

a) En cada grupo aparecen los n elementos.
b) Un grupo se diferencia de otro únicamente en el orden de colocación de los elementos.

Supongamos que disponemos de siete letras distintas.

Calcular cuántas cadenas de siete caracteres se pueden formar usando todos coincide, obviamente, con el número de ordenaciones posibles de las siete letras.

Evidentemente, cada configuración se diferencia de las demás únicamente en el orden de colocación de los elementos.

¿Pero cuántas posibles configuraciones/ordenaciones (al margen de que tengan sentido o no) podemos formar?

Vayamos paso a paso:

Para primera posición podemos escoger una de las siete letras. Para la segunda posición podemos escoger una de las seis letras restantes. Para la tercera, disponemos de cinco letras…

En resumen, el número de permutaciones es 7×6×5×4×3×2×1.

En general, dados n elementos distintos, el número de permutaciones (sin repetición), vendrá dado por n!.

Variaciones sin repetición

Llamamos #variaciones sin repetición de n elementos distintos tomados de m en m (m≤n) a cada grupo de m elementos escogidos entre los n elementos, tal que:

a) En cada grupo, los m elementos son distintos.
b) Dos grupos son distintos si difieren en algún elemento o en el orden.

Supongamos, de nuevo, que tenemos siete letras distintas y queremos obtener el número de cadenas de caracteres que se pueden formar con cuatro de nuestras letras.

Tengan sentido o no, se diferenciarán unas de otras si tienen letras distintas o difieren en el orden de colocación.

En la primera posición podemos situar cualquiera de las siete letras. En la segunda posición, podemos poner cualquiera de las seis letras restantes. Para la tercera posición quedan cinco letras. Finalmente, para la cuarta posición podemos escoger una de las cuatro últimas letras.

Así pues, el número de posibilidades es 7×6×5×4. Esto no es exactamente un factorial, pero… ¡es un cociente de factoriales!

En particular, 7×6×5×4 = 7!/(3!). Además, observa que 3! = (7-4)!.

En general, dados n elementos distintos, el número de variaciones (sin repetición) de n elementos distintos tomados de m en m (siendo m≤n), vendrá dado por n!/((n-m)!).

Combinaciones sin repetición

Llamamos #combinaciones sin repetición de n elementos tomados de m en m, (m≤n) a cada una de las distintas agrupaciones de m elementos de manera que:

a) En cada grupo entren m elementos distintos.
b) Dos grupos son distintos si difieren en algún elemento.

Si dos permutaciones (o variaciones) se diferencian por el orden de colocación de sus elementos, ahora el orden no tiene ninguna importancia.

Es decir, ahora no nos fijamos en el orden de colocación de las letras, sino solamente en qué letras aparecen.

En otras palabras, dos combinaciones son distintas solo si hay algún elemento distinto.

Por ejemplo, si escogiéramos tres letras en el conjunto de siete letras entre las que están a, b y c, entonces consideraríamos que abc, acb, bac, cab, bca y cba son la misma configuración.

Imagínate, por ejemplo, que siete amigos/as se reúnen y discuten sobre qué tres de ellos/as se encargan de preparar la cena. ¿No dará lo mismo que se encarguen Ana, Luis y Eva que Luis, Ana y Eva o Luis, Eva y Ana? (y todas las demás posibilidades).

En otras palabras, lo que queremos es saber cuántas formas existen de escoger tres personas de las siete personas que hay en total (sin importar el orden en que se resulten seleccionadas). Esto da lugar a las combinaciones sin repetición.

De hecho, fíjate en esto:

El conjunto vacío, solo contiene un subconjunto: el vacío (1).

El conjunto {a} formado por un elemento contiene el subconjunto vacío y el mismo {a} (1 1).

El conjunto {a,b} contiene el vacío, dos subconjuntos de un elemento y el mismo {a,b} (1 2 1).

Así aparecen, de manera natural, los números combinatorios y es así como podemos formar el triángulo de Pascal o de Tartaglia.

Pero... ¿y si quiero calcular el número de combinaciones de una gran cantidad de elementos? ¿Debo construir el triángulo? ¡Menudo tostón! ¡Nooo!

El número combinatorio n sobre m es la cantidad de subconjuntos de m elementos distintos que se pueden formar a partir de un conjunto de n elementos distintos. Estas cantidades se pueden obtener como n!/(m!(n-m)!).

¿Qué relación tiene esto con las variaciones y permutaciones?

Bien, supongamos que escogemos tres letras en un conjunto de siete letras entre las que están a, b y c, entonces abc, acb, bac, cab, bca y cba serían diferentes variaciones (debido al orden), pero la misma combinación (porque el orden no importa).

Variaciones 6 – 1 Combinaciones

Es evidente entonces que hay menos combinaciones que variaciones. En nuestro ejemplo, cada combinación da lugar a seis variaciones. Pero, ¿por qué seis?

Observa que seis es, de hecho, el número de posibles ordenaciones (permutaciones) de los tres elementos, es decir, 3!.

No en vano, la fórmula de las combinaciones n!/(m!(n-m)!) se obtiene dividiendo el número de variaciones de n elementos tomados en m en m (n!/(n-m)!) por el número de permutaciones de m elementos (m!).

Veamos un ejemplo completo.

Supongamos que tenemos un conjunto inicial con cinco elementos distintos ({a,b,c,d,e}, por ejemplo) y deseamos calcular el número de combinaciones de elementos tomados de dos en dos.

Aunque el número de combinaciones es menor, comencemos calculando el número de variaciones: 5!/(5-2)! = 5×4 = 20.

Esto quiere decir que podemos considerar veinte parejas de caracteres (a saber: ab, ba, ac, ca, ad, da, ae, ea, bc, cb, bd, db, be, eb, cd, dc, ce, ec, de, ed).

Sin embargo, como combinaciones en las que no importa el orden, ab es indistinguible de ba, ac es indistinguible de ca, ad es indistinguible de da… etc.

Y, por tanto, hay la mitad de combinaciones que de variaciones.

Esta “mitad” corresponde a que, por cada combinación, hay dos maneras distintas de ordenar cada pareja de símbolos, cada una de las cuales da lugar a una variación. Esta cantidad coincide con el número de permutaciones de dos elementos: 2!=2.

Variaciones 2 – 1 Combinaciones

¿Sabrías calcular el número de combinaciones que se pueden construir de un conjunto de siete elementos distintos tomados de cuatro en cuatro?

Hay 7!/(7-4)! = 7!/3! = 7×6×5×4 = 840 variaciones posibles, pero solo

7!/(4!(7-4)!) = 7!/(4!3!) = 840 /(4×3×2×1) = 35 combinaciones.

Tal y como has visto, a lo largo de estos tuits hemos supuesto siempre que los elementos del conjunto inicial son distintos (sin repetición).

El caso en que los elementos puedan repetirse será objeto de otro hilo.

Si has llegado hasta aquí, muchas gracias. Ya ves que hacen falta muchos dedos para contar 😊😊😊

Todo el texto, junto a los gifs, están publicados en mi blog:

elultimoversodefermat.wordpress.com/2020/10/08/vam…