Calculate $\sum_{|\cup S|=k}(-1)^{|S|+1}$ where $S$ is a non-empty subset of $X=\{\{a_1,a_2\},\{a_2,a_3\}\cdots,\{a_n,a_{n+1}\}\}$ Let $x_i=\{a_i,a_{i+1}\}\ (1 \leq i \leq n)$ and $X=\{x_1, \cdots, x_n\}$. Given $k$, I'd like to ask how to calculate $\sum_{|\cup S|=k}(-1)^{|S|+1}$ where $S$ is a non-empty subset of $X$?
The problem can be transformed into $\sum_{t}\sum_{\substack{|\cup S|=k\\|S|=t}}(-1)^{|S|+1}=\sum_{t}(-1)^{t}\sum_{\substack{|\cup S|=k\\|S|=t}}1$. The last summation can be interpreted as counting how many length-$n$ binary strings with  $t$ ones such that the number of consecutive "11" substrings is $2t-k$. But it's still hard to perform calculation.
 A: There is a nice algebraic way to do this by constructing a regular language (or equivalently an appropriate finite automaton) and extracting a generating function from it.  Such problems are inherently linear, so we know that we'll come out with a rational generating function and it will be routine to find explicit expressions for its coefficients or analyze its growth. 
We're working towards getting a trivariate generating function $P(u,x,y)$ where the coefficient of $u^a x^b y^c$ encodes the number of ways to divide the $n$ sets into $b$ sets that form exactly $c$ contiguous blocks. $P(u,x,y)$ will contain more than enough information to answer your question.  Indeed, observe that the number of elements covered by a choice of $b$ sets forming $c$ contiguous blocks is always $b + c$.  Thus, setting $Q(u,z) = -P(u,-z,z)$, we see that the $u^nz^k$ coefficient of $Q$ encodes precisely the sign-weighted sum of ways to cover $k$ elements in the problem of size $n$, i.e. the coefficients of $Q$ will be precisely what you are asking about.
To get this power series we first construct a finite automaton that steps through the sets one at a time, at step either selecting or skipping the next set.  We want the automaton to be able to keep track of three pieces of information:  how many steps it has taken ($u$), how many sets it has chosen ($x$), and how many contiguous blocks it has formed ($y$).  The automaton needs $2$ states, so that it knows whether the next set it chooses is being added to a previous block or is the beginning of a new block.  
Here is a diagram of the automaton. As an example, suppose $n = 5$ and the automaton was choosing the arrangement $\{a_2, a_3\}, \{a_3, a_4\}, \{a_5, a_6\}$.  The automaton would reach this by the sequence NO YES YES NO YES, and the variable encoding would progress as $u, u^2xy, u^3x^2y, u^4x^2y,u^5x^3y^2$.

Let's call the right state the $F$ state ($F$ for free) and the left state the $B$ state ($B$ for block).  Let $L_F(u,x,y)$ be the trivariate generating function whose coefficient $u^a x^b y^c$ is the number of ways that the automaton can produce that variable encoding by starting at the $F$ state (by construction, these are the numbers we're interested in).  Define $L_B(u,x,y)$ similarly, but instead counting the number of ways starting at the $B$ state.
Algebraically, we can read off a system of equations relating the two generating functions.  The first equation intuitively says that when we are in the $F$ state, we can encode $uxy$ and go to the $B$ state, or we can encode $u$ and remain in the $F$ state, or we can stop.  Similarly for the second equation.  
$$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$$
(Note: If our problem had, for example, the additional restriction that we always had to choose the $n$th set, then we could easily incorporate that into our method; it would translate to saying that the automaton cannot stop on the $B$ state, and thus to removing the '$+1$' from the $L_B$ defining equation.)
We can solve for $L_F$! After some arithmetic manipulations you come out with
$$L_F(u,x,y) = \frac{1+uxy-ux}{1 -ux - u - u^2xy + u^2x}$$
Finally, as said above, we can specify / forget about information to get $$Q(u,z) = -L_F(u,-z,z) = -\frac{1 - uz^2 + uz}{1+uz - u+ u^2z^2 - u^2z}$$
As a sanity check, note that we do have $Q(u,1) = -1$, which is a relief because in theory we should have $Q(u,1) =\sum_k\sum_{|\cup S|=k}(-1)^{|S|+1} = \sum_k {n \choose k } (-1)^{k+1}$.  
With $Q(u,z)$ in hand it becomes easy to analyze these numbers any which way.  
For example, letting $a_{k,n}$ be the coefficient of $z^k u^n$, we immediately get the recurrence relation
$$a_{k,n} = a_{k, n-1} - a_{k-1,n-1} + a_{k-1,n-2} - a_{k-2,n-2}$$
with the initial conditions $$a_{0,n} = -1, a_{1,n} = 0, a_{2,n} = n$$ (and of course $a_{k,n} = 0$ if $k > n+1$)
