Ytukyg

How many binary sequences of length n are there, such that they contain precisely k 01 pairs? How to approach it? I have no idea how to deal with it.

Hint:

A binary sequence of length $n$ that starts with a $0$ and has $k$
$01$ pairs can be represented by a tuple $left(a_{1},dots,a_{m}right)$
where $minleft{ 2k,2k+1right} $ and the $a_{i}$ are positive
integers with $sum_{i=1}^{m}a_{i}=n$.

Examples for $n=11$ and $k=3$:

• 
  $00101101110$ is represented by $(2,1,1,2,1,3,1)$
  


• 
  $00101101111$ is represented by $(2,1,1,2,1,4)$
  

A binary sequence of length $n$ that starts with a $1$ and has $k$
$01$ pairs can be represented by a tuple $left(a_{1},dots,a_{m}right)$
where $minleft{ 2k+1,2k+2right} $ and the $a_{i}$ are positive
integers with $sum_{i=1}^{m}a_{i}=n$.

Examples for $n=11$ and $k=2$:

• 
  $11101101110$ is represented by $(3,1,2,1,3,1)$
  


• 
  $11101101111$ is represented by $(3,1,2,1,4)$
  

So to be counted are the number of such sums $sum_{i=1}^{m}a_{i}=n$.

This can be done by applying stars and bars.

Using $z$ for zeros and $w$ for ones we have from first principles the
generating function

$$(1+w+w^2+cdots) sum_{qge 0} (z+z^2+cdots)^q (w+w^2+cdots)^q u^q
\ times (1+z+z^2+cdots).$$

Here the variable $u$ marks $01$ pairs. This is

$$frac{1}{1-w}
left(sum_{qge 0} frac{z^q}{(1-z)^q} frac{w^q}{(1-w)^q} u^qright)
frac{1}{1-z}
\ = frac{1}{1-w}
frac{1}{1-uzw/(1-z)/(1-w)}
frac{1}{1-z}
\ = frac{1}{(1-w)(1-z)-uzw}.$$

At this point we no longer need the distinction between zeros and
ones, getting

$$frac{1}{(1-z)^2-uz^2}.$$

As a sanity check we should get all of them when we put $u=1$ and
indeed we have

$$frac{1}{1-2z+(1-u)z^2} = frac{1}{1-2z},$$

accounting for all $2^n$ strings. To extract the coefficient we write

$$frac{1}{(1-z)^2} frac{1}{1-uz^2/(1-z)^2}$$

so that

$$[z^n] [u^k]frac{1}{(1-z)^2} frac{1}{1-uz^2/(1-z)^2}
= [z^n] frac{1}{(1-z)^2} frac{z^{2k}}{(1-z)^{2k}}
\ = [z^n] frac{z^{2k}}{(1-z)^{2k+2}}
= [z^{n-2k}] frac{1}{(1-z)^{2k+2}}
= {n-2k+2k+1choose 2k+1}.$$

This is

$$bbox[5px,border:2px solid #00A000]{
{n+1choose 2k+1}.}$$

HINT

You are restricting/mandating $k$ pairs in the string to be a $10$ pair ... instead of being just any pair. So, what should be the number of all bit strings of length $n$ containing at least $k$ $10$ pairs compared to the number of all bit strings of length $n$ without any restrictions? And how do you get from that to the number of strings of length $n$ that have exactly $k$ $10$ pairs?