# 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.

• Are $a_1,a_2,\ldots,a_{n+1}$ pairwise distinct?
– user614671
Dec 2, 2018 at 12:05
• Yes. All $a_1, a_2, \cdots, a_{n+1}\$ are distinct. Dec 2, 2018 at 12:06
• In the second-to-last sentence, I think you mean "[...] length-$\color{red}{(n+1)}$ binary strings with $\color{red}{k}$ ones such that [...] is $\color{red}{2t+1-k}$." Dec 2, 2018 at 21:30
• No. There are $2^n$ possibilities for the choice of $S$, and each consecutive "11" substring will reduce the size of $\cup S$ by one. Dec 3, 2018 at 3:38
• I just left a lengthy possible solution, but maybe I should have first asked: what kind of answer are you looking for? Dec 3, 2018 at 8:00

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