OIA-Wiki

Lo que hablaremos de combinatoria, será relacionado a cómo saber “cuántas distintas posibilidades hay”, o “cuántos conjuntos distintos existen tales que...”.

Por ejemplo, dada la palabra “OLIMPIADA”, cuántas palabras distintas existen con esas letras (dos letras “A”, una “O”, etc.), que comiencen con la letra “O”? (Obviamente no tienen por qué estar en el diccionario)

En ese ejemplo, estamos hablando de permutaciones de las letras. Una permutación de un conjunto, es un conjunto que contienen los mismos elementos que el inicial, cada uno aparece la misma cantidad de veces en ambos conjuntos, pero puede variar el orden.

Entonces, por ejemplo, cuántas permutaciones distintas tiene el conjunto $\{1, 2, 3\}$? Bueno, pensemos que tenemos tres lugares a ocupar. En el primero, podemos ubicar cualquiera de esos tres elementos. Luego, para el segundo lugar, nos quedan dos posibilidades (las que no usamos en el primer lugar, ya que no vale repetir el primer elemento), y el tercer elemento estaría fijo, por descarte. Entonces tendríamos, para cada una de las $3$ posibilidades de ubicar en el primer lugar, $2$ posibilidades para el segundo lugar. Y para cada una de esas $3*2 = 6$ posibilidades, nos queda un elemento posible para ubicar al final. Por lo tanto hay $6$ permutaciones posibles. En efecto:
$\{1, 2, 3\}$
$\{1, 3, 2\}$
$\{2, 1, 3\}$
$\{2, 3, 1\}$
$\{3, 1, 2\}$
$\{3, 2, 1\}$

A este número, $3*2*1$, se lo conoce como factorial, se escribe $3! = 3*2*1$, y es muuy importante en el mundo de la combinatoria. En general, $N! = N*(N-1)*(N-2)\ldots*2*1$, con $N$ entero no negativo. Y se define $0! = 1$.

Ahora, ¿cuántas permutaciones distintas hay del conjunto $\{1, 2, 2\}$. Ahora hay que tener cuidado, ya que si contamos como antes, algunas las vamos a contar más de una vez. Por ejemplo, las primeras dos, con el $1$ al principio, quedarían iguales, ya que el elemento $2$ está repetido. Pero cuántas estamos contando dos veces? Veamos que en la manera de arriba, enumeramos todas las permutaciones pensando como si fueran todos los elementos distintos. Si acá hiciéramos lo mismo, pintando los números dos de distintos colores que tenemos un DOSROJO y un DOSAZUL, los primeros conjuntos quedarían $\{1, R, A\}$ y $\{1, A, R\}$, que ahora sería la misma permutación. En definitiva, a cada permutación distinta la estamos contando $2$ veces, una con el azul primero y otra con el rojo primero.

¿Y del conjunto $\{1, 2, 2, 2, 3, 3\}$? Analizando como recién, vemos que a cada conjunto distintos, le podemos cambiar los $2$ de orden y seguir teniendo la misma permutación. Hay $3! = 6$ de cambiar el orden de los $2$, según lo que vimos más arriba. Y además, para permutación de $2$ que hagamos, podemos permutar los números $3$, de $2! = 2$ maneras distintas (como con el rojo y el azul antes). Por lo tanto, si contamos las permutaciones repetidas, tenemos $6!$ posibilidades, pero a cada permutación distinta la estamos contanto $3!*2!$ veces. Por lo que la respuesta a la cantidad de permutaciones distintas sería $\dfrac{6!}{3!*2!}$.

En general, la cantidad de permutación de $n$ elementos donde hay $k$ elementos distintos que aparecen $c_1, c_2, \ldots, c_k$ veces (el i-ésimo aparece $c_i$ veces, con $1\leq c_i \leq n$), es $\dfrac{n!}{c_1!*c_2!*\ldots*c_k!}$. Algo interesante es que este número siempre es entero, ya que es la cantidad de permutaciones distintas.

Entonces, para responder a la pregunta sobre la cantidad de palabras distintas que empiezan con $O$, lo que podemos hacer para que el tema de la primera letra fija no nos complique, es pensar que la sacamos, miramos todas las permutaciones de las demás letras, y si a esas les agregamos la $O$ tenemos las palabras buscadas, por lo que la respuesta será la misma que buscar todas las permutaciones distintas sin la letra $O$. Entonces la respuesta sería $\dfrac{8!}{2!*2!} = 8*7*6*5*4*3*2*1/(2*1*2*1) = 100800$

¿Cuántos grupos distintos de $5$ personas podemos formar, si tenemos disponibles $9$ personas? Repitiendo la idea de arriba, tenemos $5$ lugares para llenar. Para el primero tenemos $9$ posibilidades. Luego, habiendo seleccionados a la primera persona, nos quedan $8$ posibilidades para el segundo lugar. Luego tendremos $7$ para el tercer lugar, $6$ posibilidades para el cuarto lugar, y por último nos quedarán $5$ personas, de las cuales tendremos que seleccionar una para ocupar el último lugar, habiendo $5$ posibilidades para este último. Entonces, de esta manera, a priori, tenemos $9*8*7*6*5$ posibilidades.

Ahora, al elegir a las personas $1, 2, 3, 4, 5$, estamos formando el mismo grupo que al llenar los lugares con las personas $3, 4, 1, 2, 5$, y también es el mismo grupo que al elegir a $5, 4, 3, 2, 1$. Si pensamos entonces, cuántas veces estamos eligiendo el mismo grupo, podemos ver que para cada grupo distinto, en la cuenta de arriba, $9*8*7*6*5$, estamos contando a cada grupo la misma cantidad de veces como permutaciones tiene. Y eso ya lo sabemos calcular. Como son todas las personas distintas, habrá $5!$ permutaciones distintas.

Por lo que en total, tendremos $9*8*7*6*5/5!$ grupos distintos de $5$ personas, eligiendo entre $9$. Una manera más linda de verlo, es pensar que el término de arriba es ir multiplicando desde el $9$ hacia abajo, teniendo $5$ términos, que es igual a $9!/4!$. Ese $4$ sale de que si arriba tenemos $5$ términos, a los $9$ términos de $9!$ le estamos dejando $5$, por lo que le sacamos los $9-5=4$ términos más chicos.

En términos generales, si queremos formar un grupo de $k$ personas, teniendo $n$ para elegir, hay $\dfrac{n!}{k!*(n-k)!}$ distintas formas de hacerlo.

A este número, se lo conoce como $C_k^n$, que también se escribe a veces $nCk$, $C(n,k)$ ó $\binom{N}{k}$. Algo interesante de estos números es que se los puede calcular de manera dinámica a partir de números con parámetros más chicos: $C(n,k) = C(n-1,k-1) + C(n-1,k)$ (siempre y cuando $n,k>0$). Esto se puede deducir de pensar: Bueno, quiero formar todos los grupos distintos con $k$ personas. Si miramos a la persona $1$, puede estar o no estar en nuestro grupo, obviamente. Si está, nos queda por elegir $k-1$ personas de las restantes $n-1$. Y si no está, todavía tenemos que elegir $k$ personas, pero tenemos $n-1$ posibles ya que la persona $1$ no es una opción.

Veamos un problema donde podemos usar algo de esto:

PROBLEMA

Otro problema de combinatoria: Cuántas maneras distintas hay de sumar el número $n$ con números positivos? Por ejemplo, para $n=4$, tenemos $1+1+1+1, 1+1+2, 2+2, 1+3, 4$ Lo que podemos pensar es que tenemos $n$ números $1$ escritos uno al lado del otro, y tenemos que poner barreras que separan en grupos. Entonces por ejemplo la manera $1+1+2$ sería $1 | 1 | 1 1$ .