Number of possible sequence partitioning
The problem formulation is not entirely clear. This answer assumes that the allowed subsequences are of the form $10^*1$. Other variants can be solved in a similar way.

Suppose that the original sequence is $a_1,\ldots,a_n$. Let $b(i,x)$ denote the number of ways to partition $a_1,\ldots,a_i$ into any number of subsequences of the form $10^*1$ and $x$ subsequences of the form $10^*$ (open subsequences).

Initially $b(0,0) = 1$ and $b(0,x) = 0$ for $x &gt; 0$. Let us now consider how to calculate $b(i+1,\cdot)$ given $b(i,\cdot)$. There are two possibilities to consider:


If $a_{i+1} = 0$ then a partition of $a_1,\ldots,a_i$ extends to a partition of $a_1,\ldots,a_{i+1}$ by attaching $a_{i+1}$ to any of the open subsequences. Thus $b(i+1,x) = xb(i,x)$ in this case.
If $a_{i+1} = 1$ then a partition of $a_1,\ldots,a_i$ extends to a partition of $a_1,\ldots,a_{i+1}$ in one of two ways: either it "closes" an open subsequences, or it forms a new open subsequences. Thus $b(i+1,x) = (x+1)b(i,x+1) + b(i,x-1)$.


The total number of partitions is then $b(n,0)$. Since $0 \leq x \leq n$, we can compute $b(n,0)$ in time $O(n^2)$ using dynamic programming.

As an illustration, here is a run of the algorithm on the sequence $1,0,1,1,0,1$. The columns correspond to $i$, and the rows to $x$:

$$
\begin{array}{c|cccccc}
x/i &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 \\\hline
0 &amp; 1 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 3 \\
1 &amp; 0 &amp; 1 &amp; 1 &amp; 0 &amp; 3 &amp; 3 &amp; 0 \\
2 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 12 \\
3 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 3 &amp; 0 \\
4 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 3
\end{array}
$$