Con este problema subyacente poset consta de nodos $Q\subconjunto
[n-1]$ (the set of positions where a $01$ par reside) que
representan cadenas binarias con $01$ que aparecen en las posiciones más
posiblemente algunos otros. Tenga en cuenta que los conjuntos representados en algunos $Q$son
vacío, es decir, cuando hay solapamiento entre dos o más $01$
pares, es decir, cuando existe una $m$ tal que $\{m,m+1\} \subseteq
P.$ The weights on the $Q$ are as usual $(-1)^{|P|}.$ La cardinalidad
del conjunto de cadenas de caracteres representados en $Q$ es claramente $2^{n-2|Q|}.$Para
un dado de cardinalidad $|Q|=q$ el número de nodos de $Q$ sin solapamiento
entre los componentes de los pares se obtiene mediante la colocación de un número de
espacios (que recibirá un dígito binario), posiblemente vacía, entre
el $q$ $01$ pares cuya longitud debe sumar a $n-2q:$
$$[z^{n-2t}] \frac{1}{(1-z)^{q+1}} =
{n-2t+q\elegir q} = {n-p\elegir q}.$$
(Hay dos cardinalidades aquí, la cardinalidad $|Q|=q$ de $Q$y
la cardinalidad $2^{n-2q}$ del conjunto de cadenas de caracteres representados en $Q$.)
La introducción de $M$, el conjunto de los subconjuntos de a$[n-1]$ que no contienen un
par $\{m,m+1\}$ es decir, sin superposición y recuento de las cadenas de
representada en todos los $Q\in M$ multiplicado por el peso de los rendimientos de la
la forma cerrada
$$\sum_{Q\in M} (-1)^{|P|} 2^{n-2|Q|}
= \sum_{q=0}^{\lfloor n/2\rfloor}
{n-p\elegir q} (-1)^q 2^{n-2t}.$$
Aquí hemos utilizado el hecho de que la longitud de la $n$ de la cadena impone
el enlazado $n\ge 2|Q|.$
Por otro lado, el conteo de calcular el peso total contribuido
por cada una de las $2^n$ cadenas nos encontramos con que una cadena que no tiene
instancia de la $01$ par sólo aparece en $Q=\emptyset$ , con un total de
peso $(-1)^{|\emptyset|} = 1.$ Una cadena cuyo conjunto de instancias de
el $01$ par es exactamente $P$ donde $|P|\ge 1$ aparece en todos los
$Q\subseteq P$ para un peso total de cero desde
$$\sum_{Q\subseteq P} (-1)^{|P|}
= \sum_{q=0}^{|P|} {|P|\elegir q} (-1)^p = 0.$$
Observar que esto funciona desde $P\in M$ e $Q\subseteq P$ implica $Q
\en M.$ llegamos a la conclusión de que estos pesos que la suma de la cuenta
exactamente esas cadenas con ninguna instancia de la $01$ par, estas teniendo
el peso de uno, y los otros con peso cero. Por lo tanto es igual
a
$$n+1.$$
Como un comentario, se observa que la suma no es difícil de evaluar. Nosotros
obtener
$$\sum_{q=0}^{\lfloor n/2\rfloor}
{n-p\elegir n-2t} (-1)^q 2^{n-2t}
= 2^n [z^n] (1+z)^n \sum_{q=0}^{\lfloor n/2\rfloor}
(-1)^q 2^{-2t} z^{t2} (1+z)^{-q}.$$
Aquí el coeficiente de extractor de controles de la gama y continuamos con
$$2^n [z^n] (1+z)^n \sum_{q\ge 0}
(-1)^q 2^{-2t} z^{t2} (1+z)^{-q}
\\ = 2^n [z^n] (1+z)^n
\frac{1}{1+z^2/(1+z)/4}
= 2^n [z^n] (1+z)^{n+1}
\frac{1}{1+z+z^2/4}
\\ = 2^n [z^n] (1+z)^{n+1} \frac{1}{(1+z/2)^2}
= 2^n \sum_{k=0}^n {n+1\elegir n-k} (k+1) (-1)^k 2^{-k}
\\ = 2^n \sum_{k=0}^n {n+1\elegir k+1} (k+1) (-1)^k 2^{-k}
= (n+1) 2^n \sum_{k=0}^n {n\elegir k} (-1)^k 2^{-k}
\\ = (n+1) 2^n (1-1/2)^n = n+1.$$
