0
$\begingroup$

Determine the number of unique sequences of length 15, consisting of x's and y's, and which contain either 10 consecutive x's or 5 consecutive y's. (`xyyyxyyyyyyyyyy' is an example of a sequence which should be counted).

I'm currently stuck on this question and have been getting some very large answers (e.g 46078) that I don't believe can exist.

Any assistance with the following question would be great:

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

The strings with 5 consecutive $a$s can be counted as

  • beginning with at least 5 $a$, i.e. $aaaaa$ followed by arbitrary stuff: $2^5=32$
  • beginning with $k$ arbitrary letters, followed by $baaaaa$, followed by $4-k$ arbitrary (so $0\le k\le 4$): $5\cdot 2^4$.

That makes $112$ seqeuences contaiing $aaaaa$ somewhere. There are also $112$ seqeunces with $bbbbb$. WE have to subtract those counted in both parts, i.e. $aaaaabbbbb$ and $bbbbbaaaaa$. So th etotal is $222$.

$\endgroup$
1
  • $\begingroup$ Judging by the example given it's at least 5 consecutive, does this working include that? for example: "babaaaaaab" can be counted $\endgroup$
    – lecaille
    Commented Nov 26, 2013 at 21:14
1
$\begingroup$

Say that the earliest position at which you finish a run of $5$ is $k$. If $k=5$, there are $2$ choices for the run letter and $32$ choices for the remaining letters. If $k=6,7,8,9,10$, there are $2$ choices for the run letter and $16$ choices for the remaining letters (the letter at $k-5$ must differ from the run letter, but the other four are free). For $k=10$, this count includes $a^5 b^5$ and $b^5 a^5$, whose earliest runs actually finish at $k=5$; subtract those two. The result is: $64+5\cdot 32 - 2=222$ possibilities.

$\endgroup$

You must log in to answer this question.

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