Funciones generadoras de las soluciones de $3x_1 + x_2 = n$

Question

Necesito encontrar la cantidad de soluciones con enteros no negativos a la ecuación $x_1 + x_2 + x_3 = n$ con $x_2 = 2x_1$ .

Lo transformé en $y_1 + y_2 = n$ cuando $y_1=3x_1, y_2 = x_3$

(porque $x_1 + x_2 + x_3 = n$ aquí es lo mismo que $x_1 + 2x_1 + x_3 = n$ que es $3x_1 + x_3 = n$ ).

Uso de funciones generadoras $$[x^n] = \frac {1}{(1-x^3)(1-x)}$$ que es ampliando $1-x^3$ : $$[x^n] = \frac {1}{(1-x)^2(1+x+x^2)}$$ El problema aquí es que la expansión de $(1+x+x^2)$ implica números complejos, así que no estoy seguro de cómo proceder a partir de aquí.

Answer 1

Una pista: Utilizamos el coeficiente de operador $[x^n]$ para denotar el coeficiente de $x^n$ en una serie $A(x)=\sum_{k=0}^\infty a_kx^k$ y escribir $$\begin{align*} [x^n]A(x)=[x^n]\sum_{k=0}^\infty a_kx^k=a_n \end{align*}$$

En la situación actual consideramos $$\begin{align*} [x^n]\frac{1}{(1-x)^3(1-x)}\tag{1} \end{align*}$$

Una ampliación de la otra representación $\frac{1}{(1-x)^2(1+x+x^2)}$ es posible, pero menos conveniente. En ambos casos tenemos dos series para expandir y la expansión de la serie en (1) es algo más simple.

Obtenemos $$\begin{align*} \color{blue}{[x^n]\frac{1}{(1-x)^3(1-x)}}&=[x^n]\left(\sum_{k=0}^\infty x^k\sum_{j=0}^\infty x^{3j}\right)\tag{2}\\ &=\sum_{k=0}^n [x^{n-k}]\left(\sum_{j=0}^\infty x^{3j}\right)\tag{3}\\ &=\sum_{k=0}^n [x^k]\left(\sum_{j=0}^\infty x^{3j}\right)\tag{4}\\ &=\sum_{k=0}^{\left\lfloor\frac{n}{3}\right\rfloor} 1\tag{5}\\ &\color{blue}{=\left\lfloor\frac{n}{3}\right\rfloor+1} \end{align*}$$

Comentario:

• En (2) expandimos ambas series utilizando la _expansión de la serie binomial_ .

• En (3) utilizamos la linealidad del coeficiente de y aplicar la regla $[x^{p-q}]A(x)=[x^p]x^qA(x)$ . También fijamos el límite superior de la suma de la izquierda en $n$ ya que otros índices no contribuyen al coeficiente de $x^n$ .

• En (4) cambiamos el orden de la suma de la izquierda poniendo $k\rightarrow n-k$ .

• En (5) seleccionamos el coeficiente de $x^k$ observando que sólo los múltiplos de tres proporcionan una contribución no nula.

Answer 2

Puede proceder de dos maneras. En primer lugar, puede utilizar la fórmula

$$\frac{1}{1 - x} \sum_{n} a_n x^n = \sum_n \left( \sum_{k = 0}^n a_k \right) x^n.$$

Es decir, la multiplicación por $(1 - x)^{-1}$ te da las sumas parciales de una serie. Las sumas parciales de

$$\frac{1}{1 - x^3} = 1 + x^3 + x^6 + x^9 + \cdots$$

vienen dadas por

$$(1 + x + x^2) + 2(x^3 + x^4 + x^5) + 3(x^6 + x^7 + x^8) + 4\cdots.$$

Que puede describirse como

$$[x^n] \frac{1}{(1 - x)^2(1 + x + x^2)} = \left\lfloor \frac{n}{3} \right\rfloor + 1.$$

---

La segunda forma, que es la que se pretende, utiliza la propiedad fundamental de las funciones generadoras racionales (c.f. Stanley EC1 Teorema 4.1.1 ) lo que implica que

$$[x^n] \frac{1}{(1 - x)^2(1 + x + x^2)} = (A + Bn)1^n + C\left( \cos \frac{\pi}{3} + i \sin \frac{\pi}{3} \right)^n + D \left( \cos \frac{\pi}{3} - i \sin \frac{\pi}{3} \right)^n$$

Lo que si miras los 4 primeros coeficientes te da suficiente información para determinar (aquí es útil usar un ordenador en lugar de hacerlo a mano)

$$[x^n] \frac{1}{(1 - x)^2(1 + x + x^2)} = \frac{2}{3} + \frac{1}{3}n + \frac{1}{3} \cos\left(\frac{2 n \pi}{3}\right) + \frac{1}{3 \sqrt 3} \sin\left(\frac{2 n \pi}{3}\right).$$

Entonces, utilizando la periodicidad del seno y del coseno, vemos que cuando $n \equiv 0 \pmod 3$ tenemos

$$\frac{2}{3} + \frac{1}{3}n + \frac{1}{3} = \frac{n}{3} + 1.$$

Cuando $n \equiv 1 \pmod 3$ tenemos

$$\frac{2}{3} + \frac{1}{3}n - \frac{1}{6} + \frac{1}{6} = \frac{n - 1}{3} + 1.$$

Y finalmente, cuando $n \equiv 2 \pmod 3$ tenemos

$$\frac{2}{3} + \frac{1}{3}n - \frac{1}{6} - \frac{1}{6} = \frac{n - 2}{3} + 1.$$

Estos tres casos pueden describirse conjuntamente como

$$\left\lfloor \frac{n}{3} \right\rfloor + 1.$$