Combinaciones de seleccionar n objetos con diferentes tipos k

Question

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?

Answer 1

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}. $$

Answer 2

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)

Answer 3

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}$$