1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Show us what you've done so far. $\endgroup$
    – gnasher729
    Sep 22, 2014 at 12:30
  • $\begingroup$ Familiar with triangle of Pascal? $\endgroup$
    – drhab
    Sep 22, 2014 at 12:34
  • $\begingroup$ Try recursiveness. If you know a certain pattern exists for $n$ tosses, what new patterns become possible if you toss one more coin? Do you remark an analogue with the triangle of Pascal? $\endgroup$ Sep 22, 2014 at 12:37
  • $\begingroup$ What is a "consequnce"? $\endgroup$ Sep 22, 2014 at 12:55
  • $\begingroup$ He meant a sequence. $\endgroup$ Sep 22, 2014 at 13:46

3 Answers 3

5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Thinking about your problem i am sure permutation with repetition would solve it too.

$ \frac{n!}{k!(n-k)!} $ with $k=0,...,n$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .