Find number of solutions of $x_1 \wedge x_2 \oplus x_2 \wedge x_3 \oplus ... \oplus x_{n-1} \wedge x_n = 1$

Question

I'm trying to find number of solutions of boolean equation $$x_1 \wedge x_2 \oplus x_2 \wedge x_3 \oplus ... \oplus x_{n-1} \wedge x_n = 1$$ where $\oplus$ is Exclusive or and $\wedge$ is Logical conjunction

My knowledge of combinatorics is not good enough, so my first idea was to code a program which produces correct output for further investigation.

And the output was something like this

n = 2   counter: 1
n = 3   counter: 2
n = 4   counter: 6
n = 5   counter: 12
n = 6   counter: 28
n = 7   counter: 56
n = 8   counter: 120
n = 9   counter: 240
n = 10  counter: 496
n = 11  counter: 992
n = 12  counter: 2016
n = 13  counter: 4032
n = 14  counter: 8128
n = 15  counter: 16256
n = 16  counter: 32640
n = 17  counter: 65280
n = 18  counter: 130816
n = 19  counter: 261632
n = 20  counter: 523776

After some googling, I came out with this sequence

I'm really interested about how can I solve this problem by some "counting" methods. Here's the program I wrote in case you're interested about the output (hope it is correct).

Thanks for your help.

Answer 1

Since the generalized $\bigoplus$ is true iff an odd number of terms are true, and since the terms are all of the form $x_i \land x_{i+1}$, meaning that the only true terms are of the form $1 \land 1$, here is something you can do to find the numbers in your series much more quickly (that is: without checking every possible bitstring):

Let $a_{11}^n$ be the number of solutions for $n$ where $x_n = 1$

Let $a_{10}^n$ be the number of solutions for $n$ where $x_n = 0$

Let $a_{01}^n$ be the number of non-solutions for $n$ where $x_n = 1$

Let $a_{00}^n$ be the number of non-solutions for $n$ where $x_n = 0$

You can now easily find the terms $a_{ij}^{n+1}$ on the basis of the terms $a_{ij}^{n}$.

For example, to figure out $a_{11}^{n+1}$: There are two ways you can get these:

You can add a 1 to the previous non-solutions that end with a 1, thus adding the term $1 \land 1$ at the end, thus going from an even to an odd number of terms that are true, and thus turning the non-solution to a solution.

Or you can add a 1 to the previous solutions that end with a 0, thus adding the term $0 \land 1$ at the end, thus keeping an odd number of terms that are true, and thus keeping it a solution.

Thus:

$a_{11}^{n+1} = a_{01}^n + a_{10}^n$

Likewise, you can find:

$a_{10}^{n+1} = a_{11}^n + a_{10}^n$

$a_{01}^{n+1} = a_{11}^n + a_{00}^n$

$a_{00}^{n+1} = a_{01}^n + a_{00}^n$

Now, this doesn't give you a nice formula yet, but at least you can generate your numbers real fast (since for any $n$, it is $a_{11}^n + a_{10}^n$), starting with:

$a_{11}^2 = 1$ (11 is only solution ending with 1)

$a_{10}^2 = 0$ (no solutions end with 0)

$a_{01}^2 = 1$ (01 is only non-solution ending with 1)

$a_{00}^2 = 2$ (00 and 10 are both non-solutions ending with 0)

So you get as successive numbers:

$a_{11} : 1,1,4,6,16,...$

$a_{10} : 0,1,2,6,12,...$

$a_{01} : 1,3,4,10,16,...$

$a_{00} : 2,3,6,10,20,...$

And thus your series (again, add $a_{11}^n$ to $a_{10}^n$): 1,2,6,12,28,...

And someone who is better at math than I am can probably turn this into some kind of matrix operation, and figure out a quick formula.

ADDITION

I created the multiplication matrix, observed its behavior by multiplying it by itself, and was able to generate the following hypothesis:

CLAIM: for any $n \geq 2$:

$a_{11}^n = \begin{cases} 2^{2k} &\mbox{if } n = 2k+2 \\ 2^{2k+1}-2^k & \mbox{if } n =2k+3 \end{cases}$

$a_{10}^n = \begin{cases} 2^{2k}-2^k &\mbox{if } n = 2k+2 \\ 2^{2k+1}-2^k & \mbox{if } n =2k+3 \end{cases}$

$a_{01}^n = \begin{cases} 2^{2k} &\mbox{if } n = 2k+2 \\ 2^{2k+1}+2^k & \mbox{if } n =2k+3 \end{cases}$

$a_{00}^n = \begin{cases} 2^{2k}+2^k &\mbox{if } n = 2k+2 \\ 2^{2k+1}+2^k & \mbox{if } n =2k+3 \end{cases}$

Proof of Claim by Induction:

Base: n=2, i.e. n = 2*k+2 for k=0

$a_{11}^n = 2^{2k} = 2^{2*0} = 2^0 = 1$

$a_{10}^n = 2^{2k}-2^k = 2^{2*0}-2^0 = 2^0-1 = 1-1=0$

$a_{01}^n = 2^{2k} = 2^{2*0} = 2^0 = 1$

$a_{00}^n = 2^{2k}+2^k = 2^{2*0}+2^0 = 2^0+1 = 1+1=2$

All these values are correct as shown above.

Step: We need to consider two cases:

Case 1: $n=2k+2$

By Inductive Hypothesis, we can assume:

$a_{11}^n = 2^{2k}$

$a_{10}^n = 2^{2k}-2^k$

$a_{01}^n = 2^{2k}$

$a_{00}^n = 2^{2k}+2^k$

Now let's consider $n+1 = 2k+3$:

$a_{11}^{n+1} = a_{01}^n + a_{10}^n = 2^{2k} + 2^{2k}-2^k = 2^{2k+1}-2^k$

$a_{10}^{n+1} = a_{11}^n + a_{10}^n = 2^{2k} + 2^{2k}-2^k = 2^{2k+1}-2^k$

$a_{01}^{n+1} = a_{11}^n + a_{00}^n = 2^{2k} + 2^{2k}+2^k = 2^{2k+1}+2^k$

$a_{00}^{n+1} = a_{01}^n + a_{00}^n = 2^{2k} + 2^{2k}+2^k = 2^{2k+1}+2^k$

These are all what they should be in accordance with the Claim.

Case 2: $n=2k+3$

By Inductive Hypothesis, we can assume:

$a_{11}^n = 2^{2k+1}-2^k$

$a_{10}^n = 2^{2k+1}-2^k$

$a_{01}^n = 2^{2k+1}+2^k$

$a_{00}^n = 2^{2k+1}+2^k$

Now let's consider $n+1 = 2k+4 = 2(k+1) + 2$:

$a_{11}^{n+1} = a_{01}^n + a_{10}^n = 2^{2k+1}+2^k + 2^{2k+1}-2^k = 2^{2k+2} = 2^{2(k+1)}$

$a_{10}^{n+1} = a_{11}^n + a_{10}^n = 2^{2k+1}-2^k + 2^{2k+1}-2^k = 2^{2k+2}-2^{k+1} = 2^{2(k+1)}-2^{k+1}$

$a_{01}^{n+1} = a_{11}^n + a_{00}^n = 2^{2k+1}-2^k + 2^{2k+1}+2^k = 2^{2k+2} = 2^{2(k+1)}$

$a_{00}^{n+1} = a_{01}^n + a_{00}^n = 2^{2k+1}+2^k + 2^{2k+1}+2^k = 2^{2k+2}+2^{k+1} = 2^{2(k+1)}+2^{k+1}$

Again, these are all what they should be in accordance with the Claim.

Hence, by induction, the Claim is proven.

Finally then, where $n$ is the number of variables $x_i$, we have that the number of solutions is:

$f(n) = a_{11}^n + a_{10}^n = \begin{cases} 2^{2k} + 2^{2k} - 2^k = 2^{2k+1} - 2^k &\mbox{if } n = 2k+2 \\ 2^{2k+1} - 2^k + 2^{2k+1} - 2^k = 2^{2k+2} - 2^{k+1} & \mbox{if } n =2k+3 \end{cases}$

Quick check:

$f(2) = 2^1-2^0 = 2-1 = 1$

$f(3) = 2^2-2^1 = 4-2 = 2$

$f(4) = 2^3-2^1 = 8-2 = 6$

$f(5) = 2^4-2^2 = 16-4 = 12$

$f(6) = 2^5 - 2^2 = 32-4=28$

...looks right!

Answer 2

For each assignment of values to $x_1,\ldots,x_n$ we get in induced subgraph of the path graph $P(n)$ on vertices $1,\ldots,n$: specifically, we get the subgraph that has an edge $\{k,k+1\}$ iff $x_k\land x_{k+1}=1$. Then $\bigoplus_{k=1}^{n-1}(x_k\land x_{k+1})=1$ iff the corresponding induced subgraph has an odd number of edges. In view of the COMMENTS section of OEIS A032085, this shows that we really are dealing with that sequence. Thus, if $a_n$ is the number of solutions for $n$ variables, the sequence satisfies the recurrence

$$a_n=6a_{n-2}-8a_{n-4}$$

for $n\ge 6$ with $a_2=1,a_3=2,a_4=6$, and $a_5=12$.

This is really just two interlaced instances of the recurrence $b_n=6b_{n-1}-8b_{n-2}$, one with initial values $b_1=1$ and $b_2=6$, and the other with initial values $b_1=2$ and $b_2=12$. The auxiliary equation for this recurrence is $x^2-6x+8=0$, with zeroes $2$ and $4$, and it’s easy to check that the initial values $b_1=2$ and $b_2=12$ yield the solution $b_n=4^n-2^n$. The initial values $b_1=1$ and $b_2=6$, being half as large, must then yield the solution

$$b_n=\frac12\left(4^n-2^n\right)=2^{n-1}\left(2^n-1\right)\;.$$

In terms of the original sequence we have

$$\left\{\begin{align*} a_{2k}&=2^{k-1}(2^k-1)=2^{2k-1}-2^{k-1}\\ a_{2k+1}&=4^k-2^k\;. \end{align*}\right.$$

These can be combined as

$$a_n=2^{n-1}-2^{\left\lfloor\frac{n-1}2\right\rfloor}\;.$$