0
$\begingroup$

How many binary strings of length $15$ contain the same bit in all the odd numbered positions? The positions are numbered $1, 2, \dots , 15$. Show how you arrived at your answer, which rules of counting were used etc.

I know you have to use factorials but I don't know where to start.

$\endgroup$
  • 2
    $\begingroup$ Once you set a value for the odd-numbered bits, all that matters is how many possible ways there are to fill in the even-numbered bits? How many even-numbered bits are there? How many values can these take? Hint:Factorials don't enter into it. $\endgroup$ – saulspatz Nov 2 '19 at 22:08
  • $\begingroup$ Well, you have $-a-b-c-d-e-f-g-$ where $-$ can be either $0$ or $1$ and $a,b,c,d,e,f,g$ can all be either $0$ or $1$. $\endgroup$ – fleablood Nov 2 '19 at 23:35
0
$\begingroup$

The set of all 15-length strings with the same bit in all odd locations is essentially reducing the string down to 8 bits (the first of which is the bit value corresponding to all odd indices). Obviously, we know the number of different bit strings of length 8 is $2^8=256$. To reclaim the 15-length string, we simply take the first bit and put it inbetween all of the other bit positions, as shown in the example below: $$ \underset{{\text{first bit}}}{\underbrace{1}}\underset{\text{seven "inbetween" bits}}{\underbrace{\quad0\quad1\quad0\quad1\quad1\quad0\quad1}} $$ $$ \downarrow $$ $$ \underset{\text{reclaimed 15-length string, weaving in the first bit}}{\underbrace{\underbrace1\quad0\quad\underbrace1\quad1\quad\underbrace1\quad0\quad\underbrace1\quad1\quad\underbrace1\quad1\quad\underbrace1\quad0\quad\underbrace1\quad1\quad\underbrace1}} $$ And so there are 256 different such bit strings.

$\endgroup$
0
$\begingroup$

The "rule of counting" which you must use is the product rule.

You have to choose $8$ bits; the one for the odd positions and those for positions 2,4,6,8,10,12,14.

Can you now complete the calculation?

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