Primero supongo que tiene una escalera gráfico semi-infinita (sólo el infinito en una dirección). Y yo denotar $A(n)$ el número de conectados sub-grafo que contiene el vértice $(0,0)$. Yo se calcula sumando los diferentes casos. La idea es dividir la escalera en el tramo de 3 bordes $(0,0)-(0,1)$; $(0,0)-(1,0)$ y $(0,1)-(1,1)$ que voy a llamar transversales, de la orilla inferior y superior:
- para todos los gráficos, que contiene sólo el borde inferior de la primera fase:
$$A(n-1)$$
- para todos los gráficos, que contiene sólo el borde inferior y el borde transversal en el primer tramo:
$$A(n-2)$$
- para todos la gráfica que contiene el transversal y el borde superior
$$A(n-2)$$
- Para los gráficos, que contiene las tres aristas, sabemos que están conectados por los dos nodos $(1,0)$$(1,1)$. La idea es contar el número de tramos que la contiene tanto los bordes superior e inferior (se denota $k$) y el número de transversales en esta $k$ tramos (se denota $t$). Y en el último tramo de la es sólo la parte superior o la parte inferior (por lo tanto, 2 posibilidad).
$$ \sum_{k=0}^{(n-3)/2}\sum_{t=0}^{k+1}2{k+1 \choose t} A(n-3-t-2k-1) $$
- Mismo caso, pero en donde a partir de ahora todos los tramos contienen tanto en la parte superior y la parte inferior (donde $\delta_{x,y}=1$ fib $x=y$ $0$ lo contrario):
$$ \sum_{k=0}^{(n-3)/2}\sum_{t=0}^{k+1}{k+1 \choose t} \delta_{n,3+2k+t} $$
- La única escariado caso es el caso donde tanto la parte superior e inferior están presentes pero no la transversal del borde. Procedemos como en el caso anterior, pero tenemos que estar seguros de que hay al menos transversales en los tramos que contiene tanto la parte superior e inferior.
$$ \sum_{k=0}^{(n-3)/2}\sum_{t=1}^{k+1}2{k+1 \choose t} A(n-2-t-2k-1) $$
- Mismo caso, pero en donde a partir de ahora todos los tramos contienen tanto en la parte superior y la parte inferior:
$$ \sum_{k=0}^{(n-3)/2}\sum_{t=1}^{k+1}{k+1 \choose t} \delta_{n,2+2k+t} $$
Se obtienen así que $$A(n)=A(n-1)+2A(n-2)+ \sum_{k=0}^{(n-3)/2}\sum_{t=0}^{k+1}(2{k+1 \choose t} A(n-3-t-2k-1)+ \delta_{n,3+2k+t})+\sum_{k=0}^{(n-3)/2}\sum_{t=1}^{k+1}(2{k+1 \choose t} A(n-2-t-2k-1)+ \delta_{n,2+2k+t})$$
Tenga en cuenta que la suma no están bien definidas debido a que $n-2-t-2k-1$ podría ser inferior a $0$ pero usted puede agregar la condición de $A(n)=0$$n<0$.
También se necesita la base de los casos: $A(0)=1$, $A(1)=2$ y $A(2)=4$.
Lamentablemente no tengo acceso a un software que podría resolver esto. pero si usted no pone el resultado en el comentario :) Puede ser que podemos utilizar para hacer una aproximación ... (soy un poco perezoso ahora mismo ...)
Como para el caso de bi-infinita escalera una buena aproximación es $\sum_{k=0}^n A(k).A(n-k)$, pero es un poco más compleja, ya que por ejemplo en el caso de que en el primer tramo no es sólo la parte superior e inferior, usted tiene que considerar el caso en que la conexión viene de la derecha o el caso cuando se trata formulario de la izquierda (a no contar dos veces el gráfico donde ambos conectados a la derecha y a la izquierda).
Espero que ayude un poco y que alguien va a ser capaz de dar una forma cerrada :)
