Estoy tratando de resolver el siguiente problema de Cohen Técnicas Básicas de la Teoría Combinatoria:
Una colección de $n$ líneas en el plano se dice que están en posición general, si no hay dos en paralelo y no ninguna de las tres son concurrentes. Deje $a_n$ el número de regiones en que $n$ líneas generales de la posición dividen el plano. Cómo de grande es $a_n$?
La relación de recurrencia para $a_n$ es inmediata, es decir,
$$a_{n+1}=a_n+n.$$
He estado tratando de aplicar funciones de generación para resolver esta recurrencia, pero estoy haciendo un error en alguna parte. Mi intento es el siguiente:
Deje $G(X)=\sum_{k\geq 1} a_k X^k$. Multiplicando ambos lados de la recurrencia por $X^k$ y sumando sobre todas válidas $k$ da
$$\sum_{k\geq 1}a_{k+1}X^k=\sum_{k\geq 1}a_kX^k+\sum_{k\geq 1}kX^k.$$
Utilizando el hecho de que $\frac{1}{(1-x)^2}=\sum_{k\geq 1} kX^k$, me sale
$$\sum_{k\geq 1}a_{k+1}X^k=G(X)+\frac{1}{(1-x)^2}.$$
El lado izquierdo es igual a
$$\frac{G(X)-a_1}{X}=\frac{G(X)-2}{X}$$
desde $a_1=2$. La solución para $G(X)$, me sale
$$G(X)=\frac{2-4X+3x^2}{(1-x)^3}.$$
Expansión con parciales de fracciones da
$$G(X)=\frac{3}{1-x}-\frac{2}{(1-x)^2}+\frac{1}{(1-x)^3}.$$
La transformación de este en el poder, la serie da
\begin{align} G(X)&=3\sum_{k\geq 0}X^k-2\sum_{k\geq 0} (k+1)X^k+\sum_{k\geq 0}(k+1)(k+2)X^k\\ &=\sum_{k\geq 0} (3-2(k+1)+(k+1)(k+2))X^k, \end{align} lo cual no es correcto. He tratado de empezar de nuevo, pero me parece estar haciendo un muy grave error. Los pensamientos?
Solución:
La verdadera relación de recurrencia es $a_{n+1}=a_n+(n+1)$. Deje $G(X)=\sum_{k\geq 1} a_k X^k$. Multiplicando ambos lados de la recurrencia por $X^k$ y sumando sobre todas válidas $k$ da
$$\sum_{k\geq 1}a_{k+1}X^k=\sum_{k\geq 1}a_kX^k+\sum_{k\geq 1}(k+1)X^k.$$
De problemas en términos de $G(X)$ da
$$G(X)=\frac{x(2-2x+x^2)}{(1-x)^3}.$$
Por expansión con parciales de fracciones vemos
$$G(X)=\frac{x(2-2x+x^2)}{(1-x)^3}=\frac{x}{1-x}+\frac{x}{(1-x)^3}.$$
Usando el poder de la serie de identidades $\frac{1}{2}\sum_{k\geq 1}k(k-1)X^{k-1}=\frac{x}{(1-x)^3}$$\sum_{k\geq 1}X^k=\frac{x}{1-x}$. Sustituyendo estos de alimentación de la serie en da
\begin{align} G(X)&=\frac{1}{2}\sum_{k\geq 1}k(k-1)X^{k-1}+\sum_{k\geq 1}X^k\\ &=\frac{1}{2}\sum_{k\geq 1}k(k+1)X^{k}+\sum_{k\geq 1}X^k \quad \dagger\\ &=\sum_{n\geq 1} (\binom{k+1}{2}+1)X^k. \end{align}
Por lo tanto, igualando coeficientes, tenemos $$a_n=\binom{n+1}{2}+1.$$
El paso de $\dagger$ se deduce del hecho de que el primer coeficiente de la potencia de la serie es $0$.
Nota: Esta NO es la tarea, simplemente estoy trabajando a través de ejercicios durante las vacaciones de verano. Estoy seguro de que hay otras formas de abordar el problema, pero estoy tratando de practicar el uso de funciones de generación.
