How to count specific combinations in a binary set? (Or all path in a square above some treshold)

Question

I am trying to count the number of possible combinations for a set of bits of length $n$ with some specific rules:

First bit is a $0$, last bit is a $1$. Mix of $0$ and $1$ in between.

Starting from a random combination and ending with all $1$ aligned to the left, I want to know how many possible way there is to shift $1$'s onto $0$'s on it's left (Any $0$ before the next $1$)

e.g

01101 (initial random set)

01110 (last bit shifted to the left)

10101 (second bit shifted to the left)

10110 (second bit and last bit shifted to the left)

11001 (bit 2,3 shifted to the left)

11010 (bit 2,3 and 5 shifted to the left)

11100 (bit 2,3 shifted to the left, bit 5 shifted twice)

I tried a lot of thing without success. Any hint appreciated

Thx

Edit:

It would be like finding all path from $A$ to $B$ that are on or above the red line in a square starting down from the upper left corner and reaching the right side (square which side is the number of $1$ and distance from B to top is the number of $0$). A $0$ would be a step down, and a $1$ a step to the right.

initial red path: 0101101101

another exemple:

011011

011101

011110

101011

101101

101110

110011

110101

110110

111001

111010

111100

Note: I said random but if there is no general technique, I am still interested in the case where there are no more than 2 consecutive "$1$" and no more than 1 consecutive "$0$" which would fit the above square.

Answer 1

You can use summations. Suppose you have three zeros with 1s between:

$$0\underbrace{111\cdot 111}_{k_3\text{ 1s}} 0 \underbrace{111\cdot 111}_{k_2\text{ 1s}} 0 \underbrace{111\cdot 111}_{k_1\text{ 1s}}$$

Then, the number of valid bit strings is:

$$\sum_{a_1=0}^{k_1} \sum_{a_2=0}^{k_2+a_1}\sum_{a_3=0}^{k_3+a_2} 1$$