With this problem the underlying poset consists of nodes $Q\subset
[n-1]$ (the set of positions where a $01$ pair resides) which
represent binary strings with $01$ appearing at those positions plus
possibly some others. Note that the sets represented at some $Q$ are
empty, namely when there is overlap between some two or more $01$
pairs, i.e. when there exists an $m$ such that $\{m,m+1\} \subseteq
Q.$ The weights on the $Q$ are as usual $(-1)^{|Q|}.$ The cardinality
of the set of strings represented at $Q$ is clearly $2^{n-2|Q|}.$ For
a given cardinality $|Q|=q$ the number of nodes $Q$ with no overlap
between the constituent pairs is obtained by placing some number of
spaces (which will receive a binary digit), possibly empty, between
the $q$ $01$ pairs whose length must add up to $n-2q:$
$$[z^{n-2q}] \frac{1}{(1-z)^{q+1}} =
{n-2q+q\choose q} = {n-q\choose q}.$$
(There are two cardinalities here, the cardinality $|Q|=q$ of $Q$ and
the cardinality $2^{n-2q}$ of the set of strings represented at $Q$.)
Introducing $M$, the set of subsets of $[n-1]$ that do not contain a
pair $\{m,m+1\}$ i.e. with no overlap and counting the strings
represented at all $Q\in M$ multiplied by their weight yields the
closed form
$$\sum_{Q\in M} (-1)^{|Q|} 2^{n-2|Q|}
= \sum_{q=0}^{\lfloor n/2\rfloor}
{n-q\choose q} (-1)^q 2^{n-2q}.$$
Here we have used the fact that the length $n$ of the string imposes
the bound $n\ge 2|Q|.$
On the other hand, counting by computing the total weight contributed
by each of the $2^n$ strings we find that a string that has no
instance of the $01$ pair only appears at $Q=\emptyset$ with total
weight $(-1)^{|\emptyset|} = 1.$ A string whose set of instances of
the $01$ pair is exactly $P$ where $|P|\ge 1$ appears in all
$Q\subseteq P$ for a total weight of zero since
$$\sum_{Q\subseteq P} (-1)^{|Q|}
= \sum_{q=0}^{|P|} {|P|\choose q} (-1)^q = 0.$$
Observe that this works since $P\in M$ and $Q\subseteq P$ implies $Q
\in M.$ We conclude from these weights that the above sum counts
exactly those strings with no instance of the $01$ pair, these having
weight one, and the others having weight zero. Therefore it is equal
to
$$n+1.$$
As a remark, observe that the sum is not difficult to evaluate. We
get
$$\sum_{q=0}^{\lfloor n/2\rfloor}
{n-q\choose n-2q} (-1)^q 2^{n-2q}
= 2^n [z^n] (1+z)^n \sum_{q=0}^{\lfloor n/2\rfloor}
(-1)^q 2^{-2q} z^{2q} (1+z)^{-q}.$$
Here the coefficient extractor controls the range and we continue with
$$2^n [z^n] (1+z)^n \sum_{q\ge 0}
(-1)^q 2^{-2q} z^{2q} (1+z)^{-q}
\\ = 2^n [z^n] (1+z)^n
\frac{1}{1+z^2/(1+z)/4}
= 2^n [z^n] (1+z)^{n+1}
\frac{1}{1+z+z^2/4}
\\ = 2^n [z^n] (1+z)^{n+1} \frac{1}{(1+z/2)^2}
= 2^n \sum_{k=0}^n {n+1\choose n-k} (k+1) (-1)^k 2^{-k}
\\ = 2^n \sum_{k=0}^n {n+1\choose k+1} (k+1) (-1)^k 2^{-k}
= (n+1) 2^n \sum_{k=0}^n {n\choose k} (-1)^k 2^{-k}
\\ = (n+1) 2^n (1-1/2)^n = n+1.$$
01
, add back in the sequences with two instance of01
, etc. When counting the $k$-way intersections, you will need to count the number of ways to select $k$ pairs of entries from a line of $n$. This can be thought of as the number of ways to tile a $1\times n$ rectangle with $k$ dominoes and $n-2k$ squares, which is answered by $\binom{n-k}k$. $\endgroup$ – Mike Earnest Apr 17 '19 at 16:59