# Combinatorics problem involving counting the number of certain substrings

I'm not sure if this question is suited for MO, but it does seem quite challenging to me, and is required for a research problem in chemistry I'm working on. I did try getting help from elsewhere (Cross-post on MSE), but no luck so far. So I apologize if this question is unwelcome here.

Let's say I'm making a string of $A$s and $B$s, where the number of $A$s and $B$s are $a$ and $b$ respectively. A total of $a+b \choose a$ such strings are possible. Now, I wish to know the total number of '$ABA$' and '$BAB$' substrings that occur in all such strings. How do I count this?

• How would you handle the case of overlaps? For example, would the string $ABAB$ give a count of two? – Joel Reyes Noche Jan 30 '15 at 13:01
• Any occurrence of either of those substrings would add to the count. So yes, $ABAB$ would give a count of two. – Train Heartnet Jan 30 '15 at 13:11
• If ever you edit your question again, include the combinatorics-on-words tag; that might lead to more attention. (But perhaps do it a few hours or days from now.) – Joel Reyes Noche Jan 30 '15 at 13:19
• I suppose that substring in your question means factor and not subsequence. – J.-E. Pin Apr 6 '15 at 15:01

## 1 Answer

The number of sequences with ABA or BAB at one specific place is $$\binom{a+b-3}{a-2}+\binom{a+b-3}{a-1}=\binom{a+b-2}{a-1}.$$ Hence the total number of ABA and BAB is $$(a+b-2)\binom{a+b-2}{a-1}.$$

• Thank you for your answer! :) But couldn't there be strings amongst the $a+b \choose a$ strings, in which the $ABA$ or $BAB$ substrings occur more than once? This calculation doesn't take them into account, does it? – Train Heartnet Jan 30 '15 at 14:37
• Of course there exist strings with more than one substring ABA and BAB and the calculation does take this into account. – user35593 Jan 30 '15 at 20:33
• User35593's argument is basically equivalent to the "linearity of expectation". What you want to do is for each string, count # positions with ABA or BAB; and then add up over strings. What this does instead is for each position it asks how many strings have an ABA or BAB in that position; and then adds this up. It's equivalent to having a grid of numbers and then adding the rows first before adding the columns; or vice versa. – Anthony Quas Jan 30 '15 at 21:57
• Absolutely the correct answer to the question as asked. For more detailed statistics, the Goulden-Jackson cluster method (which is hard to explain in a comment - but the phrase is a good start for google) could be used in this, and many similar contexts. – Michael Albert Jan 30 '15 at 23:56
• Oh, I understand now. Thank you! :) – Train Heartnet Jan 31 '15 at 13:14