Calcular $\sum_{|\cup S|=k}(-1)^{|S|+1}$ $S$ Dónde está un subconjunto no vacío de $X=\{\{a_1,a_2\},\{a_2,a_3\}\cdots,\{a_n,a_{n+1}\}\}$

Question

Deje $x_i=\{a_i,a_{i+1}\}\ (1 \leq i \leq n)$ e $X=\{x_1, \cdots, x_n\}$. Dado $k$, me gustaría preguntarle cómo calcular el $\sum_{|\cup S|=k}(-1)^{|S|+1}$ donde $S$ es un no-vacío es subconjunto de a$X$?

El problema se puede transformar en $\sum_{t}\sum_{\substack{|\cup S|=k\\|S|=t}}(-1)^{|S|+1}=\sum_{t}(-1)^{t}\sum_{\substack{|\cup S|=k\\|S|=t}}1$. La última suma se puede interpretar como contar cuántas longitud-$n$ cadenas binarias con $t$ , que el número consecutivo de "11" subcadenas es $2t-k$. Pero aún así es difícil realizar el cálculo.

Answer 1

Hay un bonito algebraicas manera de hacer esto mediante la construcción de un lenguaje regular (o, equivalentemente, una adecuada autómata finito) y la extracción de una generación de función de ella. Tales problemas son inherentemente lineal, por lo que sabemos que vamos a salir con un racional de generación de función y va a ser rutina para encontrar las expresiones explícitas para sus coeficientes o analizar su crecimiento.

Estamos trabajando hacia la obtención de un trivariate de generación de función $P(u,x,y)$ donde el coeficiente de $u^a x^b y^c$ codifica el número de maneras de dividir el $n$ pone en $b$ conjuntos que se forman exactamente $c$ bloques contiguos. $P(u,x,y)$ contendrá información más que suficiente para responder a su pregunta. De hecho, se observa que el número de elementos cubiertos por una selección de $b$ conjuntos formando $c$ bloques contiguos siempre es $b + c$. Por lo tanto, la configuración de $Q(u,z) = -P(u,-z,z)$, vemos que el $u^nz^k$ coeficiente de $Q$ codifica precisamente el signo-suma ponderada de las formas para cubrir $k$ elementos en el problema de tamaño de $n$, es decir, los coeficientes de $Q$ será precisamente lo que usted está preguntando acerca de.

Para obtener este poder de la serie en primer lugar, construir un autómata finito que los pasos a través de los conjuntos de a uno por vez, en el paso de seleccionar o saltarse el siguiente juego. Queremos que el autómata a ser capaces de seguir la pista de las tres piezas de información: cuántos pasos ha tomado ($u$), el número de conjuntos que ha elegido ($x$), y cuántos bloques contiguos que se ha formado ($y$). El autómata necesidades de $2$ estados, para que sepa si el siguiente conjunto se elige a un bloque anterior o es el comienzo de un nuevo bloque.

Aquí está un diagrama del autómata. Como un ejemplo, suponga $n = 5$ y el autómata fue la elección de la disposición de $\{a_2, a_3\}, \{a_3, a_4\}, \{a_5, a_6\}$. El autómata iba a llegar por la secuencia NO SÍ sí NO SÍ, y la variable codificación sería el progreso como $u, u^2xy, u^3x^2y, u^4x^2y,u^5x^3y^2$.

Vamos a llamar el derecho del estado de la $F$ estado ($F$ gratis) y el de la izquierda del estado de la $B$ estado ($B$ para el bloque). Deje $L_F(u,x,y)$ ser el trivariate de generación de función cuyo coeficiente de $u^a x^b y^c$ es el número de maneras en que el autómata puede producir la variable codificación a partir de la $F$ estado (a través de la construcción, estos son los números que nos interesa). Definir $L_B(u,x,y)$ de manera similar, pero en lugar de contar el número de maneras de partida en la $B$ estatal.

Algebraicamente, se puede ver un sistema de ecuaciones que relacionan las dos funciones de generación. La primera ecuación intuitivamente dice que cuando estamos en el $F$ estado, podemos codificar $uxy$ e ir a la $B$ estado, o podemos codificar $u$ y permanecer en el $F$ estado, o nos puede detener. De igual manera para la segunda ecuación.

$$L_F(u,x,y) = uxyL_B(u,x,y) + uL_F(u,x,y) + 1$$ $$L_B(u,x,y) = uxL_B(u,x,y) + uL_F(u,x,y) + 1$$

(Nota: Si nuestro problema, por ejemplo, la restricción adicional de que siempre tuvimos para elegir el $n$th, entonces se podría incorporar fácilmente que en nuestro método; esto significaría decir que el autómata no puede detenerse en la $B$ estado y por lo tanto a la eliminación de la '$+1$' de la $L_B$ definición de ecuación.)

Podemos resolver para $L_F$! Después de algunas manipulaciones aritméticas se sale con la

$$L_F(u,x,y) = \frac{1+uxy-ux}{1 -ux - u - u^2xy + u^2x}$$

Finalmente, como se dijo anteriormente, podemos especificar / olvidarse de información para obtener el $$Q(u,z) = -L_F(u,-z,z) = -\frac{1 - uz^2 + uz}{1+uz - u+ u^2z^2 - u^2z}$$

Como una comprobación de validez, tenga en cuenta que tenemos $Q(u,1) = -1$, lo cual es un alivio porque en teoría deberíamos tener $Q(u,1) =\sum_k\sum_{|\cup S|=k}(-1)^{|S|+1} = \sum_k {n \choose k } (-1)^{k+1}$.

Con $Q(u,z)$ en la mano, se convierte en fácil de analizar estos números de cualquier manera.

Por ejemplo, lo $a_{k,n}$ ser el coeficiente de $z^k u^n$, de inmediato se obtiene la relación de recurrencia $$a_{k,n} = a_{k, n-1} - a_{k-1,n-1} + a_{k-1,n-2} - a_{k-2,n-2}$$ con las condiciones iniciales $$a_{0,n} = -1, a_{1,n} = 0, a_{2,n} = n$$ (and of course $a_{k,n} = 0$ if $k > n+1$)