Extraer coeficientes para resolver la relación de recurrencia

Question

Extraer coeficientes para resolver la relación de recurrencia

Matemáticas
combinatoria
Matemáticas discretas
funciones generadoras
relaciones de recurrencia
coeficientes binomiales

piper22

Tengo dificultades para moverme de la función generadora, $h(x)$ , expresado en forma de fracciones parciales (que creo haber encontrado con éxito) a la forma cerrada de la relación de recurrencia, $e_n$ .

La relación de recurrencia es: $e_0=e_1=1, e_2=2$ , y $e_n=3e_{n-1}-3e_{n-2}+e_{n-3}$ .

He calculado la función generadora, $h(x)$ , como: $h(x)=\frac{1-2x+2x^2}{1-3x+3x^2-x^3}$ .

Aplicando fracciones parciales, obtener: $h(x)=\frac{2}{1-x}+\frac{2}{(1-x)^2}+\frac{1}{(1-x)^3}$ .

Por Wolfram, sé que $e_n=\frac{1}{2}(n^2-n+2)$ , pero no puedo ver cómo los coeficientes de $x_n$ se extraen de los términos para llegar a esta solución (con la excepción del primer término de la fracción parcial, que claramente se convierte en $2$ ).

Respuestas (2)

Extraer coeficientes para resolver la relación de recurrencia

Rob Pratt · Answer 1

La función generadora a aplicar aquí es

\sum_{norte = 0}^{\infty} (\binom{metro + norte}{norte}) X^{norte} = \frac{1}{(1 - X)^{metro + 1}},

$\sum_{n=0}^\infty \binom{m+n}{n}x^n = \frac{1}{(1-x)^{m+1}},$ que tiene varias pruebas recientes aquí .

El $m=0$ caso es el que ya conocías. Ahora usa el $m=1$ y $m=2$ casos.

Usuario · Answer 2

Pista:

{(\frac{1}{1 - X})}^{'} = \frac{1}{(1 - X)^{2}}

$\left(\frac{1}{1-x}\right)' = \frac1{(1-x)^2}$

y

{(\frac{1}{(1 - X)^{2}})}^{'} = \frac{2}{(1 - X)^{3}}

$\left( \frac1{(1-x)^2} \right)' = \frac2{(1-x)^3}$

Veo el punto que estás diciendo, pero no estoy seguro de cómo aplicar este hecho para resolverlo.
¡Esto tiene sentido para mí ahora! En efecto, desplazamos la serie de potencias dada por $\frac{1}{1-x}$ en un grado cada vez que tomamos la derivada. Entonces, para $\frac{2}{(1-x)^3}$ , hemos desplazado la serie de potencias en dos grados. Los OGF para cada serie se derivan directamente de esta observación. ¡Gracias por ayudarme a conectar los puntos!

Extraer coeficientes para resolver la relación de recurrencia

piper22

Respuestas (2)

Rob Pratt

Usuario

piper22

piper22

Contando las formas en la cuadrícula si uno puede moverse de (x,y)(x,y)(x,y) a (x+a,x+b)(x+a,x+b)(x+a, x +b) para x,y,a,b≥0x,y,a,b≥0x,y,a,b\geq 0 arbitrario.

Prueba combinatoria de x(n)=∑nk=1L(n,k)(x)kx(n)=∑k=1nL(n,k)(x)kx^{(n)} = \sum_{k = 1}^n L(n,k)(x)_k

¿Trayectorias de coeficientes binomiales?

Dos relaciones en serie, cada una implica a la otra - del libro de particiones de Andrews

Prueba combinatoria (y algebraica) de una identidad que involucra números Lah

Sobre el número de Stirling de segunda clase

Encontrar una relación de recurrencia sobre un diccionario dado

Problema combinatorio: bolas negras y blancas divididas en k grupos con límites, y luego seleccionando una secuencia de solo bolas negras.

Una versión generalizada del principio de exclusión de inclusión usando una identidad binomial

Una suma de números de Stirling del segundo tipo