3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Are $a_1,a_2,\ldots,a_{n+1}$ pairwise distinct? $\endgroup$
    – user614671
    Dec 2, 2018 at 12:05
  • $\begingroup$ Yes. All $a_1, a_2, \cdots, a_{n+1}\ $ are distinct. $\endgroup$
    – Hang Wu
    Dec 2, 2018 at 12:06
  • $\begingroup$ 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}$." $\endgroup$ Dec 2, 2018 at 21:30
  • $\begingroup$ 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. $\endgroup$
    – Hang Wu
    Dec 3, 2018 at 3:38
  • $\begingroup$ I just left a lengthy possible solution, but maybe I should have first asked: what kind of answer are you looking for? $\endgroup$ Dec 3, 2018 at 8:00

1 Answer 1

2
$\begingroup$

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

enter image description here

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .