Dado ordenado de secuencias de 0's y 1's de longitud n. En cuántos de ellos no hay dos 0 de pie uno al lado del otro? Podría usted hacer si n=25.
Sé que esto puede ser resuelto mediante el uso de la recursividad. Yo no estoy familiarizado con la resolución de ecuaciones en recurrencia. Este podría ser hecho de otra manera?
El Goulden-Jackson Clúster Método es un método conveniente para derivar una generación de función para problemas de este tipo.
Tenemos en cuenta las palabras de longitud $n\geq 0$ construido a partir de un alfabeto $$\mathcal{V}=\{0,1\}$$ and the set $\mathcal{B}=\{00\}$ de malas palabras que no pueden ser parte de las palabras que estamos buscando.
Que se derivan de una función de $F(x)$ con un coeficiente de $x^n$ el número de ganas de palabras de longitud $n$. Según el periódico (p.7) la generación de la función $F(x)$ es \begin{align*} F(x)=\frac{1}{1-dx-\text{weight}(\mathcal{C})} \end{align*} con $d=|\mathcal{V}|=2$, el tamaño de las letras del alfabeto y con el peso numerador $\mathcal{C}$ con \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[00]) \end{align*}
Calculamos de acuerdo con el documento \begin{align*} \text{weight}(\mathcal{C}[00])&=-x^2-\text{weight}(\mathcal{C}[00])x \end{align*} \begin{align*} \text{weight}(\mathcal{C}[00])=-\frac{x^2}{1+x}\\ \end{align*}
De la siguiente manera:
Una generación de función $F(x)$ para el número de palabras construido a partir de $\{0,1\}$ que no contienen la subword $00$ es \begin{align*} F(x)&=\frac{1}{1-dx-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-2x+\frac{x^2}{1+x}}\\ &=\frac{1+x}{1-x-x^2}\\ &=1+2x+3x^2+5x^3+8x^4+13x^5\\ &\qquad+21x^6+34x^7+55x^8+89x^9+144x^{10}+\cdots\tag{1} \end{align*}
La última línea (1) se calculó con Wolfram Alpha y vemos que los coeficientes son los números de Fibonacci $F_n$ a partir de con $F_2=1$.
Llegamos a la conclusión: La generación de la función $F(x)$ es
\begin{align*} \bbox[10px,border:2px solid blue]{ F(x)=\frac{1+x}{1-x-x^2}=\sum_{n=0}^\infty F_{n+2}x^n } \end{align*}
y el número de cadenas binarias de longitud $n=25$ que no contienen la subcadena $00$ es el número de Fibonacci
$$ \bbox[10px,border:2px solid blue]{ F_{27}=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{27}-\left(\frac{1-\sqrt{5}}{2}\right)^{27}\right)=196148 } $$
$$ $$
Addon 2016-09-01: Debido a un comentario de OP algunos detalles sobre el cálculo de \begin{align*} \text{weight}(\mathcal{C}[00])=-\frac{x^2}{1+x}\tag{1} \end{align*}
Un acceso directo de la siguiente se indica en una nota al final.
El tema principal es el de forma adecuada frente a las superposiciones de las malas palabras. Para ello vamos a introducir algo de la terminología. Deje $w=w_1w_2\ldots w_n$ ser una palabra compuesta de $n$ personajes. Definimos \begin{align*} weight(w)&:=x^{length(w)}=x^n\\ HEAD(w)&:=\{w_1,w_1w_2,\ldots,w_1w_2\ldots w_{n-1}\}\\ TAIL(w)&:=\{w_n,w_{n-1}w_n,\ldots,w_nw_{n-1}\ldots w_2\}\\ OVERLAP(u,v)&:=HEAD(u)\cap TAIL(v) \end{align*}
Ejemplo: $w=00$
Ya que debemos tener en cuenta que sólo una mala palabra $00$ vemos un ejemplo con $w=u=v=00$.
Obtenemos \begin{align*} weight(00)&=x^{length(00)}=x^2\\ HEAD(00)&=\{0\}\\ TAIL(00)&=\{0\}\\ OVERLAP(00,00)&:=HEAD(00)\cap TAIL(00)=\{0\}\tag{2} \end{align*}
Si $x\in HEAD(v)$ escribimos \begin{align*} v&=xx^\prime\\ v/x&:=x^\prime \end{align*} y definimos por conveniencia $u:v$ como suma de todos los traslapos de dos palabras $u$$v$. Podemos resumir el promedio ponderado de la izquierda-más de las partes $v/x$ al cortar se superpone. \begin{align*} u:v:=\sum_{x\in OVERLAP(u,v)}weight(v/x) \end{align*}
Tenga en cuenta que de acuerdo a (2) $$OVERLAP(00,00)=\{0\}$$ So, the calculation of $u:v$ with $u=v=00$ resultados en \begin{align*} 00:00&=\sum_{x\in \{0\}}weight(00/x)\\ &=weight(00/0)\\ &=weight(0)\\ &=x^{length(0)}\\ &=x^1 \end{align*}
Finalmente nos encontramos en el comienzo de la página 9 del documento de identidad para $weight(\mathcal{C}[v])$ $Comp(v)$ se define como el conjunto de malas palabras $u\in \mathcal{B}$ que $OVERLAP(u,v)$ no está vacía. \begin{align*} weight(\mathcal{C}[v])=-weight(v)-\sum_{u\in Comp(v)}(u:v)\cdot weight\left(\mathcal{C}[u]\right) \end{align*}
Obtenemos con $v=00$ \begin{align*} weight(\mathcal{C}[00])&=-weight(00)-\sum_{u\in Comp(00)}(u:00)\cdot weight\left(\mathcal{C}[u]\right)\\ &=-x^{length(00)}-\sum_{u\in \{00\}}(u:00)\cdot weight\left(\mathcal{C}[u]\right)\\ &=-x^{length(00)}-(00:00)\cdot weight\left(\mathcal{C}[00]\right)\\ &=-x^2-x^1\cdot weight\left(\mathcal{C}[00]\right)\tag{3}\\ \end{align*} y la afirmación (1) de la siguiente manera.
Nota: Aunque la notación se ve algo complicado. Con algunos de rutina puede omitir casi todos los cálculos. Podemos deducir (3) rápidamente por la observación de que hay una mala palabra $00$, resultando en un plazo $x^2$ y una superposición \begin{align*} 0&0\\ 00&\\ \end{align*} lo que resulta en un plazo $x^{length(0)}=x$.
Nota: Otro descripción de $HEAD, TAIL$ $OVERLAP$ con la mala palabra $ABBA$ se puede encontrar en esta respuesta.
Sólo para poner en una defensa de métodos recursivos:
Deje $A_n$ el número de "buena" secuencias de longitud $n$. Es razonablemente claro que cualquier buena secuencia (de longitud de, al menos,$2$) termina en cualquiera de las $0$ o $01$. Por supuesto, lo que precede a la final debe ser una buena secuencia de menor longitud. Por el contrario, cualquier buena secuencia de longitud $n-1$ se convierte en una buena secuencia de longitud $n$ si se anexa un $0$ y cualquier buena secuencia de longitud $n-2$ se convierte en una buena secuencia de longitud $n$ si anexa $01$. Así vemos que $$A_n=A_{n-1}+A_{n-2}$$ Which we recognize as the Fibonacci recursion. Since $A_1=2$ and $A_2=3$ it is easy to generate $A_n$ for any modest $$ n. No hay necesidad de resolver la recursividad (aunque, por supuesto que es posible).
Lo que sigue es, definitivamente, más un comentario que una respuesta, proporcionando una sugerencia en caso de otros enfoques ser demasiado difícil. Muchos de estos tipos de problemas pueden ser resueltos con expresiones regulares. En su caso tenemos el regex $$1^* (01^+)^* (0|\epsilon).$$
Ahora uso $z$ de los ceros y los $w$ para conseguir la generación de la función
$$\frac{1}{1-w} \left(\sum_{q\ge 0} z^q \frac{w^p}{(1-w)^p}\right) (1+z).$$
Este rendimientos
$$\frac{1}{1-w} \frac{1}{1-zw/(1-w)} (1+z) = \frac{1}{1-w-zw} (1+z).$$
Como los requisitos de que el problema sólo especificar la cuenta nos puede caer la distinción entre ceros y unos en este punto para obtener
$$\frac{1+z}{1-z-z^2}.$$
Ahora podemos continuar como en la respuesta por @MarkusScheuer.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
