Unfortunately I'm joining the party a bit late. I had the (what I think analytic) solution earlier, but there was no time to test it and write it down.
Introduction
What got me thinking was that is is really easy to calculate this with only one forbidden pattern. If you have a word of length n then the number of all possibilities is
$$a = 2^n$$
A forbidden pattern fixes some (say m) of the binary digits. On those places you cannot choose between 0 and 1 anymore and therefore you can calculate the number of forbidden patterns by simply taking the m fixed bits not into accout
$$p=2^{(n-m)}$$
or in our case 2^Count[patt,x]. Now you simply subtract this from a and you have the number of valid combinations. If you have two or more patterns, than this works when the pattern do not interfere. Best example is when you have the same pattern twice. Then obviously you cannot subtract this two times.
The reason for this is that the intersection of those patterns is not empty. They both have the same combinations in it and therefore, we have to take care to subtract them only once. This intersection argument remembered me of the Inclusion-exclusion principle because we basically want the same: We want to count the number of the union of a set of forbidden patterns.
Looking on the formula
$$ \begin{align} \biggl|\bigcup_{i=1}^n A_i\biggr| &= \sum_{k = 1}^{n} (-1)^{k+1} \left( \sum_{1 \leq i_{1} < \cdots < i_{k} \leq n} \left| A_{i_{1}} \cap \cdots \cap A_{i_{k}} \right| \right). \end{align} $$
shows that we only need an patternIntersection operation and a patternCount operation. The argument of the inner sum in above formula contains nothing more than to count the intersection of all pattern-Subsets of length k.
Implementation
Let's first start with something very basic: the pattern-intersection. If we have two digits xx and try to think what the intersection of the patterns x1 and 1x is, then we see, that it can only be 11. Therefore, if we want to intersect two patterns, we make this digit by digit. Let's call this function c for combine
c[x, 1] = c[1, x] = c[1, 1] = 1;
c[x, 0] = c[0, x] = c[0, 0] = 0;
c[x, x] = x;
c[0, 1] = c[1, 0] = 3;
c[3, _] := 3;
c[_, 3] := 3;
So if we have (say on the first place) a x in the one pattern and a 1 in the other, the intersection will have a 1 at this place. The only new thing is, that when patterns clash with a 1 and 0, we set this to 3 which means something like both.
Now we can define a patternIntersection which takes an arbitrary number of patterns as argument an gives their intersection as output
patternIntersection[p1_List, p2_List] := c @@@ Transpose[{p1, p2}];
patternIntersection[p1_List] := p1;
patternIntersection[p1_List, p2_List, rest__List] :=
patternIntersection[patternIntersection[p1, p2], rest]
Quick test shows what we expect:
patternIntersection[{x, x, 1, x, x, 0}, {1, x, 1, x, 0, 1}]
(* {1, x, 1, x, 0, 3} *)
Now we need a function to count the possibilities. This works as explained above: just count the x in the pattern but if there is a 3 anywhere, the count is 0. This is because there does not exists any word which has a 0 and a 1 in one place:
patternCount[p__List] := With[{pp = patternIntersection[p]},
If[FreeQ[pp, 3], 2^Count[pp, x], 0]
]
Last but not least, we need to write down the formula from the top.
countValidCombinatations[forbidden_] :=
With[{n = Length[First[forbidden]]},
2^n - Sum[(-1)^(k - 1) Total[patternCount @@@ Subsets[forbidden, {k}]],
{k, n}]
]
Examples
Now we are ready to go: Testing your example
countValidCombinatations[{{x, x, x, x, 0, x, x, 1}, {x, 1, x, x, x, 0,
x, x}, {x, 1, x, x, x, 0, x, 0}}]
(* 144 *)
Testing kguglerex
kgulerex = (ToExpression /@ Characters[#]) & /@ {"10x001x1",
"0xx0110x", "1000xx01", "01xx01x1", "00x1000x", "111101x1",
"10x00x0x", "0111x0xx", "xx001011", "10x0x010"};
countValidCombinatations[kgulerex]
(* 206 *)
or the examples with 5000 digits
l = RandomChoice[{x, 0, 1}, {10, 5000}];
N@Timing@Log[10, countValidCombinatations[l]]
(* {9.16457, 1505.15} *)