Supongamos que estoy comprando pasteles para una fiesta. Hay k diferentes tipos y tengo la intención de comprar un total de n pasteles. Cuántas combinaciones diferentes de pasteles podría llevar a la fiesta?
Respuestas
¿Demasiados anuncios?El uso de un método que a menudo se llama "estrellas y barras":
Dibujamos $n$ estrellas en fila para representar los pasteles, y $k-1$ bares de dividirlas. Todas las estrellas a la izquierda de la primera barra son las tortas del primer tipo; las estrellas entre las dos primeras barras son del segundo tipo; . . . .
**|***||*|
He aquí un ejemplo con $n=6$$k=5$. Estamos recibiendo 2 del primer tipo, 3 del segundo tipo 0 del tercer tipo, 1 de el cuarto tipo, y 0 de el quinto tipo.
Con el fin de resolver el problema, sólo tenemos que reordenar las estrellas y las barras por la elección de la $k-1$ spots para las barras de la $n+k-1$ total de puntos, por lo que nuestra respuesta es:
$$ \binom{n+k-1}{k-1}. $$
Sea g(n,k) = # combinaciones de pasteles.
Observe que:
- g(n,1) = 1. (todos los pasteles son el mismo)
- g(n,2) = n+1. (por ejemplo, para 5 pasteles, el # de pasteles de tipo 1 puede ser 0, 1, 2, 3, 4, 5)
- g(1,k) = k.
- g(2,k) = k*(k-1)/2 + k (el primer término es de dos pasteles diferentes; el segundo término es cuando ambos pasteles son la misma), siempre que k > 1. (de lo contrario g(2,1) = 1)
- g(3,k) = k * (k-1) * (k-2)/6 + k*(k-1)/2 * 2 + k (el primer término es 3 pasteles diferentes; el segundo término es 2 pasteles diferentes, con un *2 ya que hay dos opciones para que uno duplicar, el tercer término es cuando todos 3 los pasteles son el mismo), siempre que k > 2.
Si pensamos k como base en lugar de la # de pasteles, entonces, este problema es equivalente a la expresión de la # de distintas n-números de un dígito en base k, cuyos dígitos son ordenados. (por ejemplo, 1122399 es equivalente a 9921231)
Yo creo que me puedo expresar como no recursivo suma:
g(n,k) = la suma de j=1 max(n,k) de { (k elegir j) * h(n,j) }
donde h(n,j) es el número de formas de partición N pasteles utilizando j de diferentes tipos. (el término en la suma es cuando hay j distintas tortas en realidad elegidos).
Pero eso es casi tan lejos como puedo conseguir... :/
edit: parece que las combinaciones con repeticiones = ((k+n-1) n). (igual que el artículo de la wikipedia con n y k intercambiar)
Supongamos que usted tiene $n$ artículos y $k$ papeleras. Usted necesita $k-1$ separadores para obtener el $n$ elementos en la $k$ papeleras. Hay $(n + k - 1)!$ permutaciones de pedidos $n$ artículos y $(k-1)$ separadores. Las permutaciones de la $n$ elementos no importan, y las permutaciones de la $(k-1)$ separadores no importa, así que tendrás que dividir por $n!$ $(k-1)!$
Por lo tanto usted tiene $$\frac{(n + k - 1)!}{n!(k-1)!} = \binom{n+k-1}{k-1}$$