<s>[INST] Combinatorics: How many distinct binary strings of length 16 are possible if the zeroes must appear in groups of even number? I am trying to solve two combinatorics problems. May you help me?
First problem,
How many distinct binary strings of length 16 are possible if the zeroes must appear in groups of even number?
I think that the key is to see that there can be even number of zeroes or odd number of zeroes. The total number of possible lists is 2^16. Half of them has even number of zeroes. Thus the answer is 2^15.
Second problem,
What if the zeroes need to be in pairs? 
Then lists that start with 01 are not allowed. Also strings that have 101, or 10001, or 1000001, etc. are not allowed. I have been thinking that if the number of zeroes need to be in pairs... The number of ones need to be in pairs, as well!
Then we just need to use the same strategy. We divide the original 16 in squares of size 2. Then we have 8 squares. The total number of possible lists is 2^8. All are even, of course, because 0 is even too.
Is my reasoning correct? Thank you for everything!
 [/INST] In order to count the number of strings of length $16$  having even runs of $0$s resp. pairs of $0$s we consider words
with no consecutive equal characters at all.
These words are called Smirnov words or Carlitz words. (See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.) 
A generating function for the number of Smirnov words over a binary alphabet is given by
\begin{align*}
\left(1-\frac{2z}{1+z}\right)^{-1}\tag{1}
\end{align*}

First problem: Even runs of $0$s
We replace occurrences of $0$ in a Smirnov word by an even number of zeros.  This corresponds to a substitution of
  \begin{align*}
z&\longrightarrow z^2+z^4+z^6+\cdots=\frac{z^2}{1-z^2}\tag{2}\\
\end{align*}
   and we replace occurrences of $1$ in a Smirnov word by any run of $1$'s with length $\geq 1$.
  \begin{align*}
z&\longrightarrow z+z^2+z^3+\cdots=\frac{z}{1-z}\tag{3}\\
\end{align*}
We obtain by substituting (2) and (3) in (1) a generating function A(z)
  \begin{align*}
A(z)&=\left(1-\frac{\frac{z^2}{1-z^2}}{1+\frac{z^2}{1-z^2}}-\frac{\frac{z}{1-z}}{1+\frac{z}{1-z}}\right)^{-1}\\
&=\frac{1}{1-z-z^2}\\
&=1+z+2z^2+3z^3+5z^4+8z^5+13z^6\cdots+\color{blue}{1597}z^{16}+\cdots
\end{align*}

with $A(z)$ a generating function of the Fibonacci numbers.

Second problem: All runs of $0$ having length $2$
We can do a similar approach as above. Here we use the substitution
\begin{align*}
z&\longrightarrow z^2\tag{4}\\
z&\longrightarrow z+z^2+z^3+\cdots=\frac{z}{1-z}\tag{5}\\
\end{align*}
We obtain by substituting (4) and (5) in (1) a generating function B(z)
  \begin{align*}
B(z)&=\left(1-\frac{z^2}{1+z^2}-\frac{\frac{z}{1-z}}{1+\frac{z}{1-z}}\right)^{-1}\\
&=\frac{1+z^2}{1-z-z^3}\tag{6}\\
&=1+z+2z^2+3z^3+4z^4+6z^5+9z^6\cdots+\color{blue}{406}z^{16}+\cdots
\end{align*}

The series expansion of $A(z)$ and $B(z)$ was done with the help of Wolfram Alpha.

We can derive a recurrence relation from the generating function easily and we obtain from (6) (similarly as it is shown in @MarkoRiedel's answer)
  \begin{align*}
[z^n]B(z)(1-z-z^3)=[z^n](1+z^2)=0
\end{align*}
  and conclude
  \begin{align*}
g_n-g_{n-1}-g_{n-3}&=0\\
g_0&=g_1=1\\
g_2&=2
\end{align*}

Finally we look at an example and consider the number of valid words of length $6$.

We obtain nine solutions
  $$\begin{array}{cccccc}
1&1&1&1&1&1\\
\color{blue}{0}&\color{blue}{0}&1&1&1&1\\
1&\color{blue}{0}&\color{blue}{0}&1&1&1\\
1&1&\color{blue}{0}&\color{blue}{0}&1&1\\
1&1&1&\color{blue}{0}&\color{blue}{0}&1\\
1&1&1&1&\color{blue}{0}&\color{blue}{0}\\
\color{blue}{0}&\color{blue}{0}&1&\color{blue}{0}&\color{blue}{0}&1\\
\color{blue}{0}&\color{blue}{0}&1&1&\color{blue}{0}&\color{blue}{0}\\
1&\color{blue}{0}&\color{blue}{0}&1&\color{blue}{0}&\color{blue}{0}\\
\end{array}
$$
  in accordance with $[z^6]B(z)=9$.

</s>