3
$\begingroup$

Given a bit string of length $20$, how many ways can such a string be generated if either all 0's or all 1's need to be grouped together in the string?

A few examples of strings that would be considered legal are $$000 \ldots 0\qquad\text{or} \qquad 001110 \ldots 0 \qquad \text{or} \qquad 1100 \ldots 11 \qquad \text{or} \qquad1110000 \ldots 0$$

I've tried a couple different ideas, but I keep running into issues with duplicate strings.

One method I used would be to imagine that there are $22$ spaces and $2$ slashes that need to go somewhere within these spaces to separate the numbers. The slashes could go before the string starts, resulting in either all 1's or all 0's depending on which number starts. I'll list some examples of this below. $$//00000 \ldots 0 \qquad \text{or} \qquad //1111 \ldots 1 \qquad \text{or} \qquad 11 \ldots /000000/\ldots 1$$

With this method, we have $2$ cases that are the same, its just either picking if 1 or 0 leads. Because of that I'm calculating $2\binom{22}{2}$. But like I said, there are issues with this method. For example, when both slashes come before the string, the string that is generated would be the same as if the slashes came after the string.

I appreciate any ideas on where I should go from here or if I'm completely wrong and should just start over with some other method.

$\endgroup$
  • 4
    $\begingroup$ you can separate the cases where you have only one block (either all 1's or all 0's), two blocks (setting a slash between two of the 20 positions) and three blocks (setting the left slash and then setting the right slash in regards to the position of the left one) $\endgroup$ – otto Jun 12 at 22:44
  • 1
    $\begingroup$ actually you use your way of putting two slashes in 22 possible positons. start by setting the left one, which is not allowed to have position 22 (to remove redundance). then set the right one with respect to the position of the left one $\endgroup$ – otto Jun 12 at 23:11
  • 1
    $\begingroup$ Welcome to MathSE. This tutorial explains how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Jun 13 at 1:16
11
$\begingroup$

For each such string, join its ends to form a necklace. Each necklace has at most one region of 1s and at most one region of 0s, and is characterized by the number of 1s (0 through 20).

Apart from the all-0 and all-1 necklaces, each necklace (there are 19 remaining) can be cut in 20 places, yielding distinct valid strings. The constant necklaces yield the same string no matter where you cut. So, the total number of strings is:

$$ 1 + 1 + 19 \cdot 20 = 382 $$

$\endgroup$
  • 3
    $\begingroup$ This is now my favorite answer. $\endgroup$ – David K Jun 13 at 2:29
  • 1
    $\begingroup$ I agree with @DavidK. $\endgroup$ – N. F. Taussig Jun 13 at 2:32
6
$\begingroup$

Let's follow otto's suggestion.

There are two ways to choose the first digit in the bit string.

Since all the $0$s or all the $1$s must be together, there are either $0$, $1$, or $2$ transitions between blocks of identical digits.

If there are no transitions, we do not need to place a divider. There is one way to do this.

If there is one transition, we must choose one of the $19$ places between successive digits in the $20$-digit bit string in which to place the divider between the blocks.

If there are two transitions, we must choose two of the $19$ places between successive digits in the $20$-digit bit string in which to place the dividers between the blocks.

Hence, there are $$\binom{2}{1}\left[\binom{19}{0} + \binom{19}{1} + \binom{19}{2}\right]$$ bit strings of length $20$ such that all the $0$s or all the $1$s are together in the bit string.

$\endgroup$
2
$\begingroup$

Using your idea of $22$ spaces, you not only have the ambiguity between $//\square\cdots\square$ and $\square\cdots\square//$ (where each $\square$ represents a space where you will put a digit), you also have to be concerned about how you distinguish $\square//\square\cdots\square$ from both $//\square\cdots\square$ and $/\square/\square\cdots\square.$ (If each $/$ denotes a change from $0$ to $1$ or vice versa then $\square//\square$ is the same pattern as $//\square\square$ but if either $\square/\square$ or $\square//\square$ denotes that the second $\square$ is different from the first $\square$ then $\square//\square$ and $/\square/\square$ are the same pattern.)

You can almost fix this by requiring that the two $/$s not be adjacent. Then the only ambiguity you have is between $/\square\cdots\square/\square\cdots\square$ and $\square\cdots\square/\square\cdots\square/.$ There are $19$ of each of those patterns, you want to keep one set and remove the other, so subtract $19$ from the number of ways to put $2$ non-adjacent objects in $22$ spaces, which is $\binom{21}{2}$; with two choices for the first digit this makes the number of bit strings $$ 2\left(\binom{21}{2} - 19\right).$$

Another almost-fix is to require that there be at least one digit after each $/.$ This gets rid of the $\square\cdots\square/\square\cdots\square/$ patterns so you don't have to subtract those, but it also gets rid of $/\square\cdots\square/,$ so you have to add $1$ to count that pattern. This gives the answer $$ 2\left(\binom{20}{2} + 1\right).$$

Notice that $\binom{21}{2} = \binom{20}{2} + \binom{20}{1} = \binom{19}{2} + 2\binom{19}{1} + \binom{19}{0},$ so both the results in this answer are equal to $$ 2\left(\binom{19}{2} + \binom{19}{1} + \binom{19}{0}\right) = 2\times 191,$$ which has also been shown correct in another answer. What you will not be able to do is to come up with a combinatorial argument producing a single binomial coefficient that gives the answer when multiplied by $2$, because $191$ is a prime number and the only binomial coefficients with that value are $\binom{191}{1}$ and $\binom{191}{190}.$

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