-1
$\begingroup$

Find the number of strings consisting of only a and b which have

  • P occurrence of aa
  • Q occurrence of ab
  • R occurence of ba
  • S occurence of bb.

For example strings aabbaababa have

  • aa 2 times
  • ab 3 times
  • bb 1 time
  • ba 3 times

for example answer for ( P : 1 , Q : 1 ,R : 2 ,S: 1 ) is 5 .

$\endgroup$
  • $\begingroup$ What's your alphabet? You want them presumably to have a fixed length? $\endgroup$ – Patrick Stevens Jan 29 '16 at 19:43
  • $\begingroup$ @PatrickStevens There will automatically be a fixed length, which is $P+Q+R+S + 1$, as long as there are no other letters. $\endgroup$ – Arthur Jan 29 '16 at 19:44
  • $\begingroup$ Duplicate of this question $\endgroup$ – Logophobic Jan 30 '16 at 11:35
0
$\begingroup$

First, $Q=R$ or $|Q-R|=1$; the first happens when the string begins and ends with $a$ or begins and ends with $b$; the second when the first and last characters are different.

In the case $Q=R$, there are $Q$ occurrences of $ab$ and $Q$ of $ba$. Assuming the string starts and ends with $a$, there are then $Q+1$ runs of $a$'s and $Q$ runs of $b$'s. In order for $Q+1$ runs of $a$'s to yield $P$ occurrences of $aa$, there must be $P+Q+1$ $a$'s split into $Q+1$ runs. Using stars and bars, there are $\binom{P+Q}{Q}$ ways of doing that. Similarly there must be $S+Q$ $b$'s split into $Q$ runs, and there are $\binom{S+Q-1}{Q-1}$ ways of doing that. So if the string starts and ends with $a$, there are $\binom{P+Q}{Q}\binom{S+Q-1}{Q-1}$ such strings. If the string begins and ends with $b$, we get $\binom{S+Q}{Q}\binom{P+Q-1}{Q-1}$.

The case $Q = R\pm 1$ can be analyzed similarly. If $Q=R+1$, then the string starts with $a$ and ends with $b$, so there are $Q$ occurrences of $ab$ and $R=Q-1$ of $ba$. There are $Q$ runs each of $a$ and $b$. So there are $P+Q$ $a$'s split into $Q$ runs, for $\binom{P+Q-1}{Q-1}$ possibilities, and $S+Q$ $b$'s split into $Q$ runs, for $\binom{S+Q-1}{Q-1}$ possibilities. So in total we get $\binom{P+Q-1}{Q-1}\binom{S+Q-1}{Q-1}$ ways. Finally, if $Q=R-1$, then the string starts with $b$ and ends with $a$, so we get the same answer as previously with $P$ and $S$ switched, and $Q$ and $R$ switched. This is $$\binom{S+R-1}{R-1}\binom{P+R-1}{R-1} = \binom{S+Q}{Q}\binom{P+Q}{Q}.$$

So the total number of such strings is $$ \begin{cases} \binom{P+Q}{Q}\binom{S+Q-1}{Q-1} + \binom{S+Q}{Q}\binom{P+Q-1}{Q-1},&Q=R \\ \binom{P+Q-1}{Q-1}\binom{S+Q-1}{Q-1},&Q=R+ 1 \\ \binom{P+Q}{Q}\binom{S+Q}{Q},&Q=R-1. \end{cases} $$

To answer the OP's question below, the case $P=Q=R=1$, $S=2$ is analyzed as follows: if the string starts and ends with $a$, there are two runs of $a$'s and one run of (three) $b$'s; the two possibilities are $aabbba$ and $abbbaa$. Similarly if it starts and ends with $b$, the possibilities are $bbbaab$, $baabbb$, and $bbaabb$. These correspond respectively to \begin{align*} \binom{P+Q}{Q}\binom{S+Q-1}{Q-1} &= \binom{1+1}{1}\binom{2+1-1}{1-1} = 2 \\ \binom{S+Q}{Q}\binom{P+Q-1}{Q-1} &= \binom{2+1}{1}\binom{1+1-1}{1-1} = 3. \end{align*}

$\endgroup$
  • $\begingroup$ @Arthur I don't think it's exactly the partition function, since partitions ignore order. $\endgroup$ – rogerl Jan 29 '16 at 19:54
  • $\begingroup$ You're right, I missed that. Stars and bars, then. Much easier. The answer is $\binom{P + Q}{Q}$. Then you have to look at the b's similarily. Then you have double that since it might as well begin and end with b as with a. $\endgroup$ – Arthur Jan 29 '16 at 19:54
  • $\begingroup$ @Arthur Thanks. That's right. $\endgroup$ – rogerl Jan 29 '16 at 19:55
  • $\begingroup$ @rogerl can you explain a bit with example ( 1 , 1 , 1 , 2 ) ( Q = R ) $\endgroup$ – hotrod Jan 29 '16 at 20:17
  • $\begingroup$ @hotrod Yes, there were a couple of mistakes. Try this against any other test cases you have. $\endgroup$ – rogerl Jan 29 '16 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.