Función de generación para las soluciones de la ecuación $ 2x_1 + 4x_2 = n$

Question

Vamos a denotar $h_n$ como el número de soulutions de la siguiente ecuación:

$$ 2x_1 + 4x_2 = n$$

donde $x_i \in \mathbb N$.

Encontrar la función generadora de la secuencia $hn$ y calcular el $h{2000}$.

He encontrado la función generadora:

$$\frac{1}{1-x^2}\cdot \frac{1}{1-x^4},$ $ pero no sé cómo expandir ahora. ¿Alguna idea?

Answer 1

Como se observa, si la generación de la función de $h_n$ $$f(x) = h_0 + h_1x + h_2x^2 + h_3x^3 + \dots + h_nx^n + \dots,$$ a continuación, $$f(x) = (1 + x^2 + x^4 + x^6 + \dots)(1 + x^4 + x^8 + x^{12} + \dots) = \frac{1}{1-x^2}\frac{1}{1-x^4}$$

Para conseguir realmente los coeficientes de $x^n$ en el anterior, se recurre a las fracciones parciales. El denominador de la anterior puede ser tenidos en cuenta en la irreductible factores, utilizando la identidad de $1-y^2 = (1+y)(1-y)$$(1+x)(1-x)(1+x^2)(1+x)(1-x) = (1+x)^2(1-x)^2(1+x^2)$. Por lo tanto, por la teoría general de fracciones parciales, $f(x)$ puede ser escrito como $$f(x) = \frac{A}{1+x\vphantom{(1+x)^2}} + \frac{B}{(1+x)^2} + \frac{C}{1-x\vphantom{(1-x)^2}} + \frac{D}{(1-x)^2} + \frac{Ex + F}{1+x^2} + \frac{Gx + H}{(1+x^2)^2}$$ donde $A, B, C, D, E, F, G, H$ son constantes. El uso de varios doloroso trucos es posible determinar las constantes, pero debido a que yo no soy de hacer esto como tarea para casa, voy a recurrir a Wolfram Alpha , que dice que la $$f(x) = \frac{1}{4(1+x)} + \frac{1}{8(1+x)^2} + \frac{1}{4(1-x)} + \frac{1}{8(1-x)^2} + \frac{1}{4(1+x^2)}.$$

Aquí los cinco términos son, respectivamente, $\frac14 \sum_n{(-1)^n x^n}$ y $\frac18 \sum_n {(-1)^n (n+1)x^n}$ y $\frac14 \sum_n x^n$ y $\frac18 \sum_n (n+1)x^n$ y $\frac14 \sum_n{(-1)^n x^{2n}}$, por lo $$h_{2000} = \frac14 (-1)^{2000} + \frac18 (-1)^{2000}2001 + \frac14 + \frac18 2001 + \frac14 (-1)^{1000} = 501.$$

[Esa es la respuesta, pero como usted puede ver, todo esto es muy doloroso proceso, que yo no se lo deseo a mi peor enemigo, que es la razón por la que yo sigo diciendo que la generación de funciones no es la mejor manera de resolver estos problemas de recuento, a pesar de los desaciertos de la primera etapa donde se obtiene algo lindo expresión para la generación de función.]

---

Edit: Solo por el contrario, la solución sin generar funciones: Claramente $n$ debe ser, por lo que estamos contando soluciones a $x + 2y = n/2$ en los números enteros no negativos. De $0 \le 2y \le n/2$ tenemos $0 \le y \le \left\lfloor \frac{n/2}{2} \right\rfloor$, y para cada una de las $y$ hay un único, $x = n/2 - 2y$ como solución. Por lo que el número de soluciones (para $n$)$1 + \left\lfloor \frac{n/2}{2} \right\rfloor$, que para $n = 2000$$1 + \left\lfloor \frac{1000}{2} \right\rfloor = 501$.

La solución, sin funciones de generación no es siempre así de simple, pero creo que este es un buen ejemplo de cómo iba bajando las funciones de generación de la ruta puede ser una mala idea si desea que los números exactos (como opuesto a asintótico de las estimaciones, por ejemplo).

Answer 2

Así que, asumiendo que la generación de la función es correcta, podemos ver que: $$\frac{1}{1-x^2}=\sum_{n=0}^\infty a_nx^n,\ a_n = \text{ 1 if 2 divides $n$, 0 otherwise}$$

$$\frac{1}{1-x^4}=\sum_{n=0}^\infty b_nx^n,\ b_n = \text{ 1 if 4 divides $n$, 0 otherwise}$$

Por lo que podemos utilizar esto para calcular el producto:

$$\frac{1}{1-x^2}\cdot \frac{1}{1-x^4}=\sum_{n=0}^\infty c_nx^n$$

Donde $c_n=\sum_{k=0}^n a_kb_{n-k}$, podemos ver $a_kb_{n-k} = $ 1 si 2 divide a $k$ y 4 divide $n-k$, 0 en caso contrario. Podemos ver que, por extraño $n$ este siempre se evalúa a 0 (comprobación de validez: esto tiene sentido!), y para $n$ tenemos 1 sólo cuando se $n-k$ es divisible por 4. Así que incluso $c_n$ es simplemente el número de $0\leq k\leq n$ tal que $n-k$ es divisible por 4. Con un poco de pensamiento, podemos ver que esto es $\lfloor \frac n 4 \rfloor +1$.

Por lo que poner en $n=2000$ nos da 501!

Answer 3

pensemos n como las siguientes variables

$n=6$

sólo una solución de $x_1=1$ $x_2=1$

$n=8$

de nuevo una solución

$x_1=2$ $x_2=1$

$n=10$

ahora tenemos las siguientes soluciones

$x_1=3$ $x_2=1$, la segunda pareja sería $x_1=1$ $x_2=2$

ahora tome $n=12$

$x_1=4$ y $x_2=1$ $x_1=2$ y $x_2=2$ así las secuencias es para este caso $1, 1, 2, 2$ no estoy seguro de que hay una relación clara,vamos a comprobar de nuevo

vamos a añadir dos más caso

$n=14$ las soluciones son

$x_1=3$ $x_2=2$ $x_1=1$ $x_2=3$ $x_1=5$ $x_2=1$, por lo que hay tres soluciones.ahora podemos conseguir

$1,1,2,2,3$

vamos a tomar $n=16$

hemos siguientes pares

1)$x_1=2$ $x_2=3$

2)$x_1=4$ $x_2=2$

3) $x_1=6$ $x_2=1$

así que yo creo que por más y más números,se aumenta en 1(número de la solución) y
se mantiene para el próximo número,como por ejemplo, aumenta el número de la solución por $1$ $n=22$ por ejemplo y también se mantiene esta cantidad de $n=24$

Answer 4

Como se dijo, es la función generadora:\begin{align} f(z) &= \frac{1}{1 - z^2} \cdot \frac{1}{1 - z^4} \ &= \frac{1}{4 (1 - z^2)} + \frac{1}{4 (1 + z^2)} + \frac{1}{2 (1 - z^2)^2} \end {Alinee el} (esto resulta de reconocer la función de generación como una fracción en $z^2$ y así dividir en fracciones parciales). Así la expansión es:\begin{align} f(z) &= \frac{1}{4} \sum{k \ge 0} \left( 1 + (-1)^k \right) z^{2 k} + \frac{1}{2} \sum{k \ge 0} (-1)^k \binom{-2}{k} z^{2 k} \ &= \frac{1}{4} \sum{k \ge 0} \left( 1 + (-1)^k \right) z^{2 k} + \frac{1}{2} \sum{k \ge 0} \binom{n + 1}{1} z^{2 k} \ &= \frac{1}{4} \sum{k \ge 0} \left( 1 + (-1)^k \right) z^{2 k} + \frac{1}{2} \sum{k \ge 0} (k + 1) z^{2 k} \end {Alinee el} esto da los coeficientes: h_n $$ =\begin{cases} 0 & \text{%#%#% odd} \ \left\lfloor \frac{n}{4} \right\rfloor + 1 & \text{%#%#% even} \end{casos} $$ así $n$.