Este problema lo he visto explicado con bagels, pero como acá en Colombia nadie sabe qué es eso (incluyéndome), lo voy a explicar con donas.

Imagínese que usted tiene que comprar 10 donas, y llega a un negocio donde venden donas de tres sabores: chocolate, arequipe y fresa. ¿De cuántas formas diferentes puede comprarlas?

Una opción puede ser comprarlas todas de chocolate. Otra puede ser 4 de chocolate, 2 de arequipe y 4 de fresa. O 1-1-8. O 5-0-5. Etcétera.

Si el negocio vendiera donas de un solo sabor, sería fácil: sólo hay una opción, comprarlas todas de ese sabor. Si vendiera dos sabores, hay varias opciones: 10-0, 9-1, 8-2, … 0-10. En total son 11 formas diferentes.

Ya con tres sabores se empieza a complicar el análisis. Se podría hacer así:

• 0 de chocolate - 10 de los otros dos sabores
• 1 de chocolate - 9 de los otros dos sabores
• …
• 10 de chocolate - 0 de los otros dos sabores

Como ya sabemos contar el caso de dos sabores, podemos calcular la cantidad de posibilidades en cada item de la lista, y al final sumarlos todos.

Sin embargo, si empezamos a aumentar la cantidad de donas o de sabores, hacerlo de esta forma se empieza a volver muy tedioso e ineficiente. Necesitamos una manera más sencilla de hacerlo.

El método de las barras y estrellas #

Visualicemos el problema de la siguiente manera: representemos las donas como estrellas, e incluyamos separaciones (barras) entre ellas para separar los sabores. Con este método podemos representar cualquier combinación de sabores, incluso cuando algún sabor es vacío.

En adelante diremos que la cantidad de donas es $n$ y la cantidad de sabores es $k$. En el ejemplo que hemos venido desarrollando, $n=10$ y $k=3$.

El truco viene aquí. Si nos damos cuenta, en el dibujo siempre hay $n$ estrellas y $k-1$ barras. En total hay $n+k-1$ símbolos. Entonces, el problema de contar las formas diferentes de comprar las donas se convierte en: teniendo $n+k-1$ símbolos, ¿de cúantas maneras diferentes puedo escoger $k-1$ de ellos para que sean barras?

Combinaciones #

El número de subconjuntos de $k$ elementos escogidos de un conjunto de $n$ elementos, se denota como $\binom{n}{k}$ y se lee como “combinaciones de $n$ en $k$”, "$n$ combinado $k$", o "$n$ escoge $k$" (traducción del inglés "$n$ choose $k$").

Por ejemplo, si tenemos un conjunto de 4 elementos ${1,2,3,4}$, los subconjuntos de 2 elementos son: ${1,2}$, ${1,3}$, ${1,4}$, ${2,3}$, ${2,4}$, ${3,4}$. En total, $\binom{4}{2} = 6$.

Otra forma de ver el significado de $\binom{n}{k}$ es: ¿si tengo $n$ elementos, de cuántas formas diferentes puedo escoger $k$ de ellos?

Dado un $n$ y $k$ arbitrarios, es posible hallar $\binom{n}{k}$ sin tener que listar todos los subconjuntos con la siguiente fórmula:

$$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $$

Volviendo al problema #

Como vimos, el problema original se redujo a escoger $k-1$ elementos de un conjunto de $n+k-1$ elementos, y esto sí sabemos hacerlo:

$$ \binom{n+k-1}{k-1} = \frac{(n+k-1)!}{n!(k-1)!} $$

Para el caso de 10 donas de 3 sabores, la respuesta es entonces: $$ \binom{12}{2} = \frac{12!}{10!2!} = 66 $$

Nota #

En combinatoria, a este problema se le conoce como k-composiciones débiles de n.