I am trying to apply overlapping subproblems and dynamic programming to permutations.

Say, we have a set of $ n$ elements in a string. Each of these elements could be a $ 1$ or a $ 0$ .

Given some string, I am trying to count the number of valid permutations- where a valid arrangement is defined as an ordering with no $ 1$ that stands alone from other 1s.

Example input string: $ 0101$

Example of valid arrangements: $ 1100, 0011, 0110$

Not valid: $ 0101, 1010, 1001$

EXPECTED OUTPUT: $ 3$

For example:

Say our input string contains four 1s and two 0s.

I suppose my difficulty is coming with defining the sub-problem. I initially thought I could set up a string with only the $ 0$ elements with slots/bins in between. $ [ ] 0 [ ] 0 [] $ , and then continue to use combinatorics to compute the number of additional arrangements possible with each 1 added in.

The first 1: 0 possibilities, because it will never have a 1 to accompany it.

Adding the 2nd 1: 3 possibilities, because the pair can go in either of the 3 slots.

Adding the 3rd 1: 0 new possibilities, because it must go with the other 2 ones, wherever they are.

Adding the 4th 1: We have enough to make 2 groups of $ 1$ s now… here is where I start getting unsure. I’d think it would be an additional 3 possibilities. $ \binom{3}{1} + \binom{3}{2} = 6$ total

Would anyone have an idea if I’m on the wrong track, or if not, how to proceed? This approach doesn’t seem like it works for larger values. Thanks!