Resolución de $x+2y+5z=100$ en números enteros no negativos

Question

No he hecho la combinatoria desde la escuela secundaria, por lo que este es un vergonzosamente simple pregunta.

Podemos resolver la ecuación de diophantine $x+y+z=100$ en números enteros no negativos el uso de las "barras y cuadros de" combinatoria método. Tenemos $100$ puntos, y queremos que el lugar 2 de la partición de los marcadores entre ellos, así que la respuesta es ${ 102 \choose 2}$. Hay una manera de generalizar esta (por un cambio de variable, tal vez) a las ecuaciones como $x+2y+5z=100$? Sé que puede manejar el caso en que tenemos que resolver en los enteros positivos, haciendo las sustituciones $x\rightarrow x+1$ y así sucesivamente, pero no puedo pensar en una manera de aplicar una técnica similar cuando los coeficientes no $1$.

Si no, hay una mancha de la forma de manejar estas más general de las ecuaciones?

Answer 1

También podemos resolverlo sin la generación de funciones de la siguiente manera.

En primer lugar, como un lema, ¿cuál es el número de no negativo de soluciones a $x + 2y = n$? Para cualquier elección de $y$ tal que $0 \le 2y \le n$, podemos tener una solución única (tome $x = n - 2y$), por lo que el número de soluciones es el número de estas decisiones, es decir, $\lfloor \frac{n}{2} \rfloor + 1$ (o, si se quiere, $\lceil \frac{n+1}{2} \rceil$).

Ahora el número de soluciones a $x + 2y + 5z = n$: por cada elección de $z$ tal que $0 \le 5z \le n$, el número de soluciones es que de $x + 2y = n - 5z$. El número total de soluciones se obtienen sumando a ellos.

Para $n = 100$, el número de $n - 5z$ toma los valores (la enumeración de los pares y los impares queridos por separado) $0, 10, \dots, 100$$5, 15, \dots, 95$, por lo que el número total de soluciones es $$\begin{align} &\phantom{=} \left(\left\lceil \frac{0+1}{2} \right\rceil + \left\lceil \frac{10+1}{2} \right\rceil + \dots + \left\lceil \frac{100+1}{2} \right\rceil\right) + \left(\left\lceil \frac{5+1}{2} \right\rceil + \left\lceil \frac{15+1}{2} \right\rceil + \dots + \left\lceil \frac{95+1}{2} \right\rceil \right)\\ &= \left(1 + 6 + \dots + 51\right) + \left(3 + 8 + \dots + 48\right) \\ &= 286 + 255 = 541. \end{align}$$

Answer 2

Usted puede resolver este problema mediante el uso de la idea de la generación de funciones; específicamente, para el ejemplo anterior, vamos a $c_n$ el número de enteros positivos soluciones de la ecuación

$$x+2y+5z=n$$

A continuación, la generación de la función $f(a)$ para la secuencia de $a_i$ es

$$f(a)=c_0+c_1a+c_2a^2+c_3a^3+...+c_na^n+...$$

Tenemos

$$f(a)=(1+a+a^2+...+a^i+...)(1+a^2+a^4+...+a^{2j}+...)(1+a^5+a^{10}+...+a^{5k}+...)$$

Los exponentes $i, j, k$ corresponden a los valores de $x, y, z$, respectivamente, en la ecuación de arriba.

Sin embargo, la expansión que el polinomio es todavía bastante incómodo. Como tal, podemos volver a escribir la fórmula de la siguiente manera

$$f(a)=\frac{1}{1-a}\frac{1}{1-a^2}\frac{1}{1-a^5}$$

El uso de fracciones parciales, se re-escribir $f(a)$ como sigue

$$f(a)=\frac{-a^4-a^3+a^2+1}{5(1-a^5)}+\frac{13}{40(1-a)}+\frac{1}{8(1+a)}+\frac{1}{4(1-a)^2}+\frac{1}{10(1-a)^3}$$

$$f(a)=\frac{1}{5}(-a^4-a^3+a^2+1)(1+a^5+a^{10}+a^{15}+...)+\frac{13}{40}(1+a+a^2+a^3+...)+\frac{1}{8}(1-a+a^2-a^3+a^4-...)+\frac{1}{4}(1+2a+3a^2+4a^3+...)+\frac{1}{10}(1+3a+6a^2+10a^3+15a^4+...)$$

Por lo tanto, $$c_{100}=\frac{1}{5}+\frac{13}{40}+\frac{1}{8}+\frac{1}{4}\times 101+\frac{1}{10}\times \binom{102}{2}=541$$