Jtdylktuy

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.

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_ksum_{|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$)