# How many binary strings of length $15$ contain the same bit in all the odd numbered positions?

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.

• 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. – saulspatz Nov 2 '19 at 22:08
• 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$. – fleablood Nov 2 '19 at 23:35

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.
You have to choose $$8$$ bits; the one for the odd positions and those for positions 2,4,6,8,10,12,14.