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$)
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
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
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.