find number of strings

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 .

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

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*}

• @Arthur I don't think it's exactly the partition function, since partitions ignore order. – rogerl Jan 29 '16 at 19:54
• 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. – Arthur Jan 29 '16 at 19:54
• @Arthur Thanks. That's right. – rogerl Jan 29 '16 at 19:55
• @rogerl can you explain a bit with example ( 1 , 1 , 1 , 2 ) ( Q = R ) – hotrod Jan 29 '16 at 20:17
• @hotrod Yes, there were a couple of mistakes. Try this against any other test cases you have. – rogerl Jan 29 '16 at 21:07