Encontrar el poder de la serie de una función racional

Question

En muchos combinatoria problemas de enumeración es posible encontrar un racional de generación de función (es decir, el cociente de dos polinomios) para la secuencia en cuestión. La pregunta está dada por la generación de función, ¿cómo podemos encontrar (algoritmos) los valores de la secuencia, es decir, los coeficientes de la potencia correspondiente de la serie?

Sé que para un racional de generación de función, la secuencia satisface la relación de recurrencia dada por los coeficientes del polinomio en el denominador, por lo que es realmente la cuestión de encontrar el finito de valores iniciales.

Answer 1

Si $$f(x) = \frac{P(x)}{Q(x)}$$ where $P,Q$ son polinomios, entonces tenemos que

$$f(x)Q(x) = P(x)$$

Ahora el uso de la fórmula de Leibniz para la diferenciación de un producto

$$\sum_{r=0}^{n} {n \choose r} f^{r}(x) Q^{n-r}(x) = P^{n}(x)$$

que se puede evaluar en $0$ $n=1,2,\dots$ y se puede obtener $(n+1)^{th}$ derivado de la $f$ $0$ desde el primer $n$ derivados del uso de la fórmula de arriba.

El coeficiente que necesita ser $\frac{f^{n}(0)}{n!}$.

Esto debe ser fácilmente realizable por un ordenador. No hay integración etc necesita.

Answer 2

Si uno es la informática de la mano, a continuación, la siguiente observación es útil: Si $f(x) = P(x)/Q(x)$ $Q(x) = x^d(1 - g(x))$ algunos $d \geq 0$ y algunos polinomio $g(x)$ (que podemos suponer que después de reescalado $P(x)$ $Q(x)$ ), a continuación, utilizando la fórmula de una serie geométrica nos encontramos con que $$f(x) = x^{-d}P(x)(1 + g(x) + g(x)^2 + \cdots ).$$ Explícita de la pluma y el papel de cómputos, yo normalmente encontramos esta es la forma más sencilla calcular la serie de Taylor para $f(x)$.

Answer 3

A veces parcial de las fracciones de descomposición es útil. Sobre todo si no son sólo simples postes, desde entonces cada parcial fracción se puede expandir en una serie geométrica.