1
$\begingroup$

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

From A to B

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.

$\endgroup$
  • $\begingroup$ Are you asking how many bitstrings there are overall who begin with a $0$ and end with a $1$? There are $2^{n-2}$. Or are you asking, given a specific bit string fitting that pattern, how many "shifts" there are where a "shift" is another arrangement arrived at from the original via a number of bitswaps of $0$'s on the left and $1$'s on the right? $\endgroup$ – JMoravitz Nov 12 '19 at 15:39
  • $\begingroup$ If it were this other question, then clearly the answer would depend on the original arrangement. 0101 for instance is a shift of 0011 so 0011 would clearly have every shift of 0101 in addition to 0101 itself and hence more shifts overall. $\endgroup$ – JMoravitz Nov 12 '19 at 15:41
  • $\begingroup$ So, 1s can only move left and 0s can only move right. In your example, you have $\{0\cdot 2, 1\cdot 3\}$ where 2 and 3 are the multiplicites of 0 and 1 respectively. For this example (and this example only), the only configuration that will not work is if the last two bits are both 1 (as that implies a 0 moved to the left). There are $$\dfrac{5!}{2!3!} = 10$$ possible arrangements, and $$\dfrac{3!}{1!2!}=3$$ arrangements where the last two bits are 1. This leaves $10-3=7$ arrangements where the bits shifted in the correct directions (or did not shift at all). $\endgroup$ – InterstellarProbe Nov 12 '19 at 15:43
  • 1
    $\begingroup$ Yes, it is called Inclusion/Exclusion $\endgroup$ – InterstellarProbe Nov 12 '19 at 19:22
  • 1
    $\begingroup$ Another way to do it is to use summations. $$\sum_{a_1=0}^1\sum_{a_2=0}^{2+a_1}\sum_{a_3=0}^{2+a_2} 1 = 30$$ What this represents is that the rightmost zero can move zero or one place to the right. The next rightmost zero can move between 0 and 2+the number of spaces the rightmost zero moved to the right. The leftmost zero can move to the right between 0 and 2+the number of spaces the middle zero moves. (The 2s in that formula are the number of bits that are 1 in between the 0s) $\endgroup$ – InterstellarProbe Nov 12 '19 at 19:22
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.