Número de soluciones enteras con restricciones duras

Question

En la jungla de puestos de math.stackexachange relacionados con este tema que he estado buscando desde hace tiempo. He leído algunos posts muy útiles sin embargo no puedo resolver mi propio problema. Mi versión de el número de soluciones enteras suena así:

Pregunta : Dejemos que $x + y + z \leq 13$ con las siguientes restricciones: $x \leq y \leq x+2$ y $x \leq z$ . Encuentre el número de posibilidades utilizando una función generadora.

En relación con este problema he encontrado esto Correo electrónico: . Lo intenté así para la ecuación $x + y + z =13$ :

Diga $z=x+z'$ , $x+2=y+x'$ y $y=x+y'$ . Sin embargo, al reemplazar esas expresiones en la ecuación, me quedé atascado con el reemplazo de $x'$ y $y'$ para $x$ y $y$ . Lo único que veo es que: $x' + y'=2$ . ¿Cómo puedo utilizar esta técnica correctamente?

¿Y qué pasa con la desigualdad? ¿Cómo se puede hacer frente a $x + y + z \leq 13$ ? Gracias por adelantado.

Answer 1

Como usted dice, las desigualdades son esencialmente sólo decir que $y=x+y', x+2=y+x', z=x+z'$ para algunos enteros no negativos $x',y',z'\in\mathbb Z_{\ge 0}$ . Entonces:

$$3x+y'+z'\le 13\iff 3x+y'+z'+A=13$$

para algún número entero no negativo $A$ .

Pero todavía no hemos utilizado $x+2=y+x'\iff x'+y'=2$ (utilizamos $y=x+y'$ ), que es sólo decir que $y'\in[0;2]$ .

Por lo tanto, la función generadora que necesitamos es

$$(1+x^3+x^6+x^9+x^{12})(1+x+x^2)(\sum_{i=0}^{13} x^i)(\sum_{i=0}^{13} x^i)$$

El coeficiente de $x^{13}$ será nuestra respuesta. Es 105 .
Para encontrar el coeficiente de las funciones generadoras, véase esta respuesta .

Desde $(1+x^3+x^6+x^9+x^{12})(1+x+x^2)=(1+x+x^2+\cdots+x^{14})$ podemos simplemente escribir nuestra función generadora como

$$\left[\left(\sum_{i=0}^\infty x^i\right)^3\right]_{x^{13}}=\left[\frac{1}{(1-x)^3}\right]_{x^{13}}=\binom{13+3-1}{13}=\binom{15}{13}=\binom{15}{2}=\frac{15\cdot 14}{2}=15\cdot 7=105$$