Aquí es una solución de uso muy básico de generación de funciones. Vamos a
calcular la generación de la función de estos subconjuntos con adyacencias
marcado e incluyen la mayoría de la aritmética.
Primero elige el primer elemento:
$$\frac{z}{1-z}.$$
A continuación, seleccione las diferencias entre los elementos posteriores, teniendo cuidado de
marca los elementos adyacentes con una diferencia de valor:
$$\sum_{q\ge 0} \left(uz + \frac{z^2}{1-z}\right)^q.$$
Finalmente observar que todos los subconjuntos último elemento menor o igual
a $n$ contribuir a la cuenta de $n$, lo que da un factor de
$$\frac{1}{1-z}.$$
Esto produce la generación de la función
$$G(z, u) =
\frac{1}{1-z} \frac{z}{1-z}
\frac{1}{1-(uz(1-z)+z^2)/(1-z)}
\\ = \frac{z}{1-z}
\frac{1}{1-z-(uz-uz^2+z^2)}
\\ = \frac{z}{1-z}
\frac{1}{1-(1+u)z-(1-u)z^2}.$$
Como una comprobación de validez que hemos
$$G(z, 1) = \frac{z}{1-z} \frac{1}{1-2z}
= -\frac{1}{1-z} + \frac{1}{1-2z}$$
así, obtenemos
$$[z^n] G(z, 1) = -1 + 2^n$$
subconjuntos sin marcas, que es la respuesta correcta ya que hemos
no se incluye el conjunto vacío en la construcción.
Ahora potencialmente atado conjuntos tenemos que un símbolo entre
valores adyacentes puede ser una coma o un guión, así que nos pusimos $u=2$, al pasar
$$G(z, 2) = \frac{z}{1-z}\frac{1}{1-3z+z^2}.$$
Con $$\rho_{1,2} = \frac{3}{2}\pm \frac{\sqrt{5}}{2}$$
esto se convierte en
$$-\frac{z}{z-1}\frac{1}{(z-\rho_1)(z-\rho_2)}.$$
El uso parcial de fracciones de residuos obtenemos
$$\frac{1}{z-1}
- \frac{1}{z\rho_1} \frac{\rho_1}{(\rho_1-1)(\rho_1-\rho_2)}
- \frac{1}{z\rho_2} \frac{\rho_2}{(\rho_2-1)(\rho_2-\rho_1)}
\\ = -\frac{1}{1-z}
+ \frac{1}{1-z/\rho_1} \frac{1}{(\rho_1-1)(\rho_1-\rho_2)}
+ \frac{1}{1-z/\rho_2} \frac{1}{(\rho_2-1)(\rho_2-\rho_1)} $$
La extracción de los coeficientes de esto podemos obtener
$$[z^n] G(z, 2) = -1
+ \rho_1^{-n} \frac{1}{(\rho_1-1)\sqrt{5}}
- \rho_2^{-n} \frac{1}{(\rho_2-1)\sqrt{5}}.$$
Podemos agregar aquí ya que esto representa el conjunto vacío.
Una mayor simplificación de los rendimientos ($\rho_1\rho_2 = 1$)
$$\rho_2^n \frac{1}{(\rho_1-1)\sqrt{5}}
- \rho_1^n \frac{1}{(\rho_2-1)\sqrt{5}}.$$
Finalmente
$$\frac{1}{(\rho_{1,2}-1)\sqrt{5}}
= \frac{1}{(1/2\pm \sqrt{5}/2)\sqrt{5}}
= \frac{1}{\sqrt{5}/2\pm 5/2}
\\ = \frac{\sqrt{5}/2\mp 5/2}{5/4-25/4}
= \frac{\pm 5/2 - \sqrt{5}/2}{20/4}
= \pm \frac{1}{2} - \frac{\sqrt{5}}{10}.$$
De este modo, obtener
$$\rho_2^n \left(\frac{1}{2} - \frac{\sqrt{5}}{10} \right)
+ \rho_1^n \left(\frac{1}{2} + \frac{\sqrt{5}}{10} \right)
\\ = \left(\frac{1}{2} + \frac{\sqrt{5}}{10} \right)
\left(\frac{3}{2} + \frac{\sqrt{5}}{2}\right)^n
+ \left(\frac{1}{2} - \frac{\sqrt{5}}{10} \right)
\left(\frac{3}{2} - \frac{\sqrt{5}}{2}\right)^n.$$
Esto da lugar a la secuencia (a partir de índice uno)
$$1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181, 10946, \ldots$$
que por cierto es OEIS A001519.
