¿Hacia la fórmula explícita de recursividad: está generando la función "única" respuesta?

Question

Estoy tratando de dibujar la fórmula explícita de $S_n$ que se define de la siguiente manera:

$S_n$ es el número de palabras de longitud n con 0, 1 y 2 de tal manera que no hay dos días consecutivos de 0 a ocurrir.

---

Yo, como yo había aprendido de las habilidades básicas en la combinatoria, acaba de llegar a el punto de la construcción recursiva relación tal que:

$$S_n = 2S_{n-1} + 2S_{n-2}$$

desde $S_n$ divide a disjuntas dos casos: uno con no 0 en la última postulan, y siempre 0 en el último lugar, a continuación, existen bijection entre el primero y 1 o 2 en el n-ésimo postulan multiplicado con $S_{n-1} $ de los casos, y también otro bijection entre el último y 1 o 2 a la n-1-th postulan multiplicado con $S_{n-2}$.

Así que Si mi dada la recursividad es correcta, el siguiente paso es cómo se podría ir más lejos en la formulación de con qué.

Yo superficialmente conoce el concepto de $OGF$, e $EGF$, y su definición formal. La generación de la función contiene sus secuencial de la información en una forma de coeficientes con el correspondiente polinomio grados como un índice (como tengo entendido).

Ahora si defino $S_n$ una forma funcional, $s(n)$, la generación de la función sería :

$$g(x) = \sum_{n=0}^{\infty}s(n)x^n$$

A continuación, vamos a poco se refieren a algunos de los términos de $S_n$:

$$1, 3, 8, 22, ...$$

Y revisar el $g(x)$:

$$g(x) = \sum_{n=0}^{\infty}s(n)x^n =\sum_{n=2}^{\infty}s(n)x^n+3x+1=2\sum_{n=2}^{\infty}s(n-1)x^n+2\sum_{n=2}^{\infty}s(n-2)x^n+3x+1 $$

Ahora, parece que el problema ha sido cambiado al resolver la ecuación funcional(no estoy seguro de que este es el término correcto)

1) ¿Cuál debe ser el siguiente paso?

2) Es la generación de función, la única enfoque hacia la fórmula explícita?

Answer 1

Supongamos, por el bien del argumento, de que su relación de recurrencia es correcta. Aviso es de una forma muy concreta: lineal, homogénea, constante coeficiente. Así, podemos tratarlo de una manera análoga a los métodos lineal constante coeficiente homogénea del ODE.

Comenzando con $S_0 = a$, $S_1 = b$, $S_n = 2S_{n-1}+2S_{n-2}$, asumimos nuestra solución es de la forma $r^n$, y tenemos: $$r^n = 2r^{n-1} + 2r^{n-2}$$ o $$r^2-2r-2 = (r-1)^2-3 = 0$$ Esto indica que tenemos las siguientes raíces de la ecuación característica: $r = 1+\sqrt{3}$, $r = 1-\sqrt{3}$, y es que nuestra solución es, por tanto, de la forma:

$$S_n = c_1(1+\sqrt{3})^n + c_2(1-\sqrt{3})^n$$ Configuración $n=0$, $S_0 = a$, y $n=1$, $S_1 = b$, tenemos: $$S_0 = c_1 + c_2 = a$$ $$S_1 = c_1(1+\sqrt{3}) + c_2(1-\sqrt{3}) = (c_1+c_2) + (c_1-c_2)\sqrt{3} = a+(c_1-c_2)\sqrt{3} = b$$ (Observe que el uso de la primera relación para simplificar el segundo ligeramente)

De inmediato fuimos a la conclusión de que: $$c_1+c_2 = a$$ $$c_1-c_2 = \frac{b-a}{\sqrt{3}}$$ Y nuestro coeficientes son por lo tanto: $$c_1 = \frac{1}{2}\left(a+\frac{b-a}{\sqrt{3}}\right),\quad\quad c_2 = \frac{1}{2}\left(a-\frac{b-a}{\sqrt{3}}\right)$$ y es que nuestra solución es entonces: $$S_n = \frac{1}{2}\left(a+\frac{b-a}{\sqrt{3}}\right)(1+\sqrt{3})^n + \frac{1}{2}\left(a-\frac{b-a}{\sqrt{3}}\right)(1-\sqrt{3})^n$$

Como en el ejemplo anterior, suponga $S_0 = 1 = a$, $S_1 = 3 = b$. La secuencia que genera es entonces: $$\{1,3,8,22,60,164,448,1224,3344,9136,...\}$$ (Esto también le permite hacer cosas como calcular el 197th plazo, que es 104868469426569085732577150729898576235889082115592545033891653100711477046912718209024)

Por desgracia, si la recurrencia no es de esta forma especial, las cosas se vuelven más complicadas, pero hay un buen número de referencias en matemáticas discretas, que se puede construir sobre estos métodos. (Por ejemplo, Hormigón Matemáticas por Knuth, Matemática Discreta Y Sus Aplicaciones por Rosen, Matemáticas Discretas, por Gallier, Matemáticas Discretas, para los Científicos de la computación por Stein et al, ...)

(Su recurrencia relación parece ser la correcta, pero yo no comprobar esto, ya que no parece que el principal foco de atención. Más bien, yo sólo estoy mostrando una alternativa para la generación de funciones en la solución de relaciones de recurrencia de este formulario, así como dar algunas referencias en caso de que se ejecuta a través de más general/complicado recurrencias.)

Answer 2

\begin{align} g(x) &=2\sum_{n=2}^{\infty}s(n-1)x^n+2\sum_{n=2}^{\infty}s(n-2)x^n+3x+1 \\ &=2\sum_{n=1}^{\infty}s(n)x^{n+1}+2\sum_{n=0}^{\infty}s(n)x^{n+2}+3x+1 \\ &=2x(g(x) - 1)+2x^2g(x)+3x+1 \\ \end{align}

El siguiente paso, después de lo que usted tiene, es turno de los índices 1 y 2. Por ejemplo, en la primera de la suma $$ \sum_{n = 2}^\infty s(n-1)x^{n} = s(1)x^2 + s(2)x^3 + \dots = \sum_{n = 1}^\infty s(n)x^{n + 1}. $$

El segundo paso es ahora el factor de una $x$$x^2$, respectivamente, y escribe las sumas en términos de $g(x)$.

Ahora se puede resolver esta ecuación para $g(x)$:

$$ g(x) = \frac{1 + x}{1 - 2x - 2x^2}. $$

Entonces queremos factorizar el denominador como $(1 - \alpha x)(1 - \beta x)$. Como se puede ver, $\alpha$ $\beta$ son los recíprocos de las raíces de $1 - 2x - 2x^2$. Por lo $\alpha$ $\beta$ son las raíces de $-2 -2x + x^2$, la inversión de los coeficientes (mostrar esto!). Estas son las $\alpha = 1 - \sqrt 3$$\beta = 1 + \sqrt 3$.

Ahora tome la fracción parcial de la descomposición:

$$ g(x) = \frac{1 + x}{1 - 2x - 2x^2} = \frac{A}{1 - \alpha x} + \frac{B}{1 - \beta x} $$

Usted puede resolver por $A$ $B$ a partir de esta ecuación, o señalando que

$$ \frac{A}{1 - \alpha x} + \frac{B}{1 - \beta x} = \sum_{n = 0}^\infty (A\alpha^n + B\beta^n)x^n $$

y la comparación con la $g(x) = s(0) + s(1)x + \cdots$ para obtener un sistema de ecuaciones que se pueden resolver.

---

Una alternativa a la recurrencia de la relación es el uso de una expresión regular. El conjunto de las cadenas del alfabeto $\{0,1,2\}$ que no contengan $00$ está dado por la expresión regular

$$ \{1,2\}^*(0\{1,2\}^+)^*\{\varepsilon,0\} $$

que tiene la generación de la función

$$ \frac{1}{1 - 2x} \frac{1}{1 - x\frac{2x}{1 - 2x}} (1 + x) = \frac{1 + x}{1 - 2x - 2x^2}. $$

Answer 3

Esto es donde las señales y los sistemas de conocimiento es muy útil. :-)

Los vectores propios son tus amigos.

\begin{align*} S_n &= 2 S_{n-1} + 2 S_{n-2} \\ \\ \begin{bmatrix} S_n \\ S_{n - 1} \end{bmatrix} &= \begin{bmatrix} 2 & 2 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} S_{n - 1} \\ s_{n - 2} \end{bmatrix} \end{align*}

Deje $\vec{S}_{n+1} = \begin{bmatrix} S_n \\ S_{n-1} \end{bmatrix}$. Ahora tenemos:

\begin{align*} \vec{S}_{n+1} &= \begin{bmatrix} 2 & 2 \\ 1 & 0 \end{bmatrix} \vec{S}_{n} \\ \\ \implica\ \ \ \vec{S}_{n+1} &= \begin{bmatrix} 2 & 2 \\ 1 & 0 \end{bmatrix}^n \vec{S}_1 \end{align*}

Estamos básicamente hacer en este momento, pero puedes calcular la potencia explícitamente por diagonalizing:

\begin{align*} \begin{bmatrix} 2 & 2 \\ 1 & 0 \end{bmatrix} x &= \lambda x \implica \lambda = 1\pm\sqrt{3} \\ \begin{bmatrix} 2 & 2 \\ 1 & 0 \end{bmatrix} &= \begin{bmatrix} 1 + \sqrt{3} & 1 \\ 1 - \sqrt{3} & 1 \end{bmatrix} \begin{bmatrix} 1 + \sqrt{3} & 0 \\ 0 & 1 - \sqrt{3} \end{bmatrix} \begin{bmatrix} 1 + \sqrt{3} & 1 \\ 1 - \sqrt{3} & 1 \end{bmatrix}^{-1} \\ \end{align*}

Así que esto significa que tenemos la respuesta $S_n$ en la primera fila de $\vec{S}_{n+1}$:

\begin{align*} \vec{S}_{n+1} &= \begin{bmatrix} 1 + \sqrt{3} & 1 \\ 1 - \sqrt{3} & 1 \end{bmatrix} \begin{bmatrix} (1 + \sqrt{3})^n & 0 \\ 0 & (1 - \sqrt{3})^n \end{bmatrix} \begin{bmatrix} 1 + \sqrt{3} & 1 \\ 1 - \sqrt{3} & 1 \end{bmatrix}^{-1} \vec{S}_1 \end{align*}

Answer 4

Como un apéndice de las otras soluciones, se obtiene finalmente

%#% $ #% Con un poco de paciencia, esto puede transformarse en

$$ S_n = \left(\frac{1}{2} + \frac{1}{\sqrt{3}}\right) \left(1 + \sqrt{3}\right)^n +\left(\frac{1}{2} - \frac{1}{\sqrt{3}}\right) \left(1 - \sqrt{3}\right)^n \enspace. $$