El problema del camarero. Combinaciones con repetición.

ENUNCIADO. Cinco amigos se reúnen en una terraza de un bar. Cada uno pide una bebida. El camarero, habiéndoles preguntado qué quieren tomar, ya en la barra para llenar la bandeja recuerda que han le han podido pedir cafés, cervezas y tónicas ( 3 tipos de bebidas ); sin embargo, ha olvidado cuántas personas han pedido café, cuántas han pedido cervezas y cuántas han pedido tónicas. ¿ De cuántas maneras pueden haberle hecho el pedido ?.

SOLUCIÓN. Podemos pensar la situación de modo que a cada tipo de bebida se le asignen personas del grupo de amigos; por consiguiente, no importa el orden de asignación, puesto que al camarero sólo le importa cuántos tipos de bebidas le han pedido; además, es evidente que varias personas pueden pedir el mismo tipo de bebida, luego el problema es de combinaciones con repetición.

Veamos una manera de plantearlo adecuada que nos ayude a pensar los cálculos de forma clara. Para ello, supongamos que distribuimos 5 símbolos iguales ( pongamos que cruces, que representan las personas ) en un conjunto de 3 compartimentos adyacentes ( los 3 tipos de bebia ), luego necesitaremos 3-1=2 símbolos para separar un compartimento de otro.

De esta manera, los posibles pedidos se codificarán de la manera siguiente:

café   |    cerveza   |   tónica 
===============================
xxx    |       x      |     x
-------------------------------
x      |       xxx    |     x
-------------------------------
xx     |       xx     |     x
-------------------------------
xxxxx  |              |     
-------------------------------
...

La primera significa que el pedido consta de 3 cafés, 1 cerveza y 1 tónica; la segunda, de 1 café, 3 cervezas y 1 tónica; la cuarta, de cinco cafés, etcétera

Por consiguiente, el problema queda reducido al de permutar entre sí $5$ cruces (x) y $3-1=2$ barras separadoras (|), luego el número de posibilidades es: $$\dfrac{(5+(3-1))!}{5!\cdot (3-1)!}=\dfrac{7!}{5!\cdot 2!}=\dfrac{7\cdot 6 \cdot 5!}{2! \cdot 5!} = \dfrac{42}{2}=21$$

La solución del problema puede generalizarse fácilmente al de $n$ personas que, en conjunto, han pedido hasta $k$ tipos de bebidas ( donde no necesariamente $n$ tenga que ser mayor o igual que $k$, y, recordemos que piden una cada uno ): $$\dfrac{(m+(n-1))!}{m!\cdot (n-1)!}$$

En los libros suele utilizarse la siguiente notación: $$\text{CR}_{k,n}=\binom{n+k-1}{k-1}=\binom{n+k-1}{n}$$ y representa la solución del problema genérico de repartir $n$ bolas idénticas en $k$ urnas, que es un caso concreto de un problema de combinaciones con repetición de $n$ objetos elegidos en $k$ clases, lo cual también puede designarse de la forma $\displaystyle \left(\binom{k}{n}\right)$.

$\square$