Distribuir 10 euros entre 5 personas

Question

¿De cuántas maneras puedes distribuir 10 euros entre 5 personas utilizando 1, 2, 5, 10, 20, 50 céntimos y 1 y 2 euros (con un suministro ilimitado de cada moneda)?

En la parte A de la pregunta no importa el tipo de monedas que le des a la gente.

Al principio pensé que podría utilizar las posibles combinaciones de conseguir $a+b+c+d+e=10000$ .

Pero esto sólo se puede utilizar cuando $a , ... , e$ puede tener todos los valores, lo que no es el caso.

Entonces pensé en utilizar funciones generadoras: Dado que cada persona recibe 2 euros, el número de formas de obtener los 2 euros por parte de cada persona debería ser el mismo Supongo que buscamos el coeficiente de $[x^{200}]$ y la función generadora es:

$$g(x)=(x^0+x^1+x^2+...)(x^0+x^2+x^4+...)(x^0+x^5+...)(x^0+x^{10}+...)(x^0+x^{20}+...)(x^0+x^{50}+...)(x^0+x^{100}+...)(x^0+x^{200}+...)$$

Para encontrar el coeficiente aquí podemos reescribirlo como $$g(x) = \frac{1}{1-x}\frac{1}{1-x^{2}}\frac{1}{1-x^{5}}\frac{1}{1-x^{10}}\frac{1}{1-x^{20}}\frac{1}{1-x^{50}}\frac{1}{1-x^{100}}\frac{1}{1-x^{200}}$$

Para lo cual podemos hacer una expresión combinatoria

$$g(x)=\sum_{k=0}^{\infty}\binom{n+k-1}{k}x^{k}\sum_{k=0}^{\infty}\binom{n+k-1}{k}x^{2k}\sum_{k=0}^{\infty}\binom{n+k-1}{k}x^{5k}\sum_{k=0}^{\infty}\binom{n+k-1}{k}x^{10k}\sum_{k=0}^{\infty}\binom{n+k-1}{k}x^{20k}\sum_{k=0}^{\infty}\binom{n+k-1}{k}x^{50k}\sum_{k=0}^{\infty}\binom{n+k-1}{k}x^{100k}\sum_{k=0}^{\infty}\binom{n+k-1}{k}x^{200k} $$

Pero para encontrar el coeficiente de $x^{200}$ aquí tardará años. Lo que me hace repensar mi estrategia. Debe haber alguna simplificación posible en alguna parte. ¿Alguien tiene una idea? ¿Tal vez una variación del primer enfoque?

Para la pregunta B, la elección de las monedas sí importa por persona (por ejemplo, la persona A no quiere ninguna moneda de 1 céntimo). Así que para este problema tendré que utilizar la función generadora.. Pero aún así, ¿cómo ?

Cualquier ayuda se agradecerá.

Answer 1

He escrito un pequeño programa. Hace un array ways con índices de $0$ a $1000$ y llenarlo con $1$ s, representando que hay una manera de dar a alguien cualquier cantidad de $0$ a $1000$ centavos usando $1$ monedas de un céntimo. Entonces, para cada índice $2$ y por encima en orden deja que ways[i]=ways[i]+ways[i-2] que dice que puedes darles $i$ centavos con $1$ y $2$ monedas de un céntimo dándoles $i-2$ céntimos y añadiendo un $2$ moneda de un céntimo o por no usar una $2$ moneda de un céntimo. Entonces, a partir de $5$ deja que ways[i]=ways[i]+ways[i-5]. Sigue así para cada tipo de moneda. Puedes hacer esto en $1000$ líneas y nueve columnas de una hoja de cálculo con copia hacia abajo. Obtengo $321335886$ en ambos sentidos.