Solving Coin Toss Problem If a coin is tossed 3 times,there are possible 8 outcomes.
HHH HHT HTH HTT THH THT TTH TTT
In the above experiment we see 1 sequnce has 3 consecutive H, 3 sequence has 2 consecutive H and 7 sequence has at least single H.
Suppose a coin is tossed n times.How many sequence we will get which contains a consequnce of H of length at least k?.How to solve this problem using recursive relation?
 A: Let $x^n(i,j)$ be the number of sequences of length $n$ with exactly $i$ as the length of the longest sequence of H's and ending in exactly $j$ H's. Then $x^n(i,j)=0$ if $i<j$ or $i\gt n$ or $j\gt n.$ We can fill in the table for $x^2(i,j)$ row $i,$ column $j:$
$$
\begin{array}{c|ccc}
 & 0 & 1 & 2 \\
\hline
0 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 \\
2 & 0 & 0 & 1 \\
\end{array}
$$
We can compute the array for $x^{n+1}$ from $x^n:$
We add an H or T to the (right) end of each sequence of length $n.$ Suppose we start with state $(i,j)$. If we add a T then the new value of $j$ will be $0$ no matter what the sequence was. The value of $i$ is unchanged. So the new state is $(i,0).$
If, instead, an H is added to the end, then $j$ increases by $1$ but $i$ will stay the same or increase by $1.$ We have $3$ cases: 
If $i=j$ then state $(i,i)$ becomes $(i+1,i+1).$
If $i>j$ then $(i,j)$ becomes $(i,j+1).$ 
And $i<j$ is not possible. 
Then the recursive equations are:
$x^{n+1}(i,0)=\sum_{j} x^n(i,j)$ 
$x^{n+1}(i,j)=x^n(i,j-1),$ for $i>j\ge 1.$
$x^{n+1}(j,j)=x^n(j-1,j-1)+x^n(j,j-1),\text { for }j\ge 1.  $
and $0$ otherwise.
For example, computing the table for $n=3,4$ and then $n=5:$
$$
\begin{array}{c|cccccc}
 & 0 & 1 & 2 & 3 & 4 & 5  \\
\hline
0 & 1 & 0 & 0 & 0 & 0 & 0 \\
1 & 7 & 5 & 0 & 0 & 0 & 0 \\
2 & 5 & 2 & 4 & 0 & 0 & 0 \\
3 & 2 & 1 & 0 & 2 & 0 & 0 \\
4 & 1 & 0 & 0 & 0 & 1 & 0 \\
5 & 0 & 0 & 0 & 0 & 0 & 1 \\
\end{array}
$$
Then compute the sum in each row. That gives the number with exactly $i$ as the largest number of consecutive H:  $1,12,11,5,2,1.$
If you want the number with $\ge i$ consecutive H's for $i=0,1,2,3,4,5$ :
$32,31,19,8,3,1.$
A: The number of binary strings of length $n$ with a sequence of ones of length at least 1 is, of course, $2^n-1$. Let's write $f(n,1)=2^n-1$. 
The number of binary strings of length $n$ with a sequence of ones of length at least 2 is tabulated at https://oeis.org/A008466 and the formula given is $f(n,2)=2^n-F_2(n+2)$. I'm writing $F_2(m)$ for the $m$th Fibonacci number. 
The number of binary strings of length $n$ with a sequence of ones of length at least 3 is tabulated at https://oeis.org/A050231 and the formula given is $f(n,3)=2^n-F_3(n+3)$. I'm writing $F_3(m)$ for the $m$th "tribonacci" number. 
The number of binary strings of length $n$ with a sequence of ones of length at least 4 is tabulated at https://oeis.org/A050232 and the formula given is $f(n,4)=2^n-F_4(n+4)$. I'm writing $F_4(m)$ for the $m$th "tetranacci" number. 
And the number of binary strings of length $n$ with a sequence of ones of length at least 5 is tabulated at https://oeis.org/A050233 and the formula given is $f(n,3)=2^{n+1}-F_5(n+6)$ [but I suspect it's supposed to be $f(n,5)=2^n-F_5(n+5)$]. I'm writing $F_5(m)$ for the $m$th "pentanacci" number. 
So I would hazard a guess that the number of binary strings of length $n$ with a sequence of ones of length at least $k$ is given by $f(n,k)=2^n-F_k(n+k)$ where $F_k(m)$ is the $k$th "$m$-nacci" number. 
A: Thinking about your problem i am sure permutation with repetition would solve it too.
$ \frac{n!}{k!(n-k)!} $ with $k=0,...,n$
