3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ How would you handle the case of overlaps? For example, would the string $ABAB$ give a count of two? $\endgroup$
    – JRN
    Jan 30, 2015 at 13:01
  • $\begingroup$ Any occurrence of either of those substrings would add to the count. So yes, $ABAB$ would give a count of two. $\endgroup$ Jan 30, 2015 at 13:11
  • $\begingroup$ 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.) $\endgroup$
    – JRN
    Jan 30, 2015 at 13:19
  • $\begingroup$ I suppose that substring in your question means factor and not subsequence. $\endgroup$
    – J.-E. Pin
    Apr 6, 2015 at 15:01

1 Answer 1

6
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$ Jan 30, 2015 at 14:37
  • $\begingroup$ Of course there exist strings with more than one substring ABA and BAB and the calculation does take this into account. $\endgroup$
    – user35593
    Jan 30, 2015 at 20:33
  • 2
    $\begingroup$ 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. $\endgroup$ Jan 30, 2015 at 21:57
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 30, 2015 at 23:56
  • $\begingroup$ Oh, I understand now. Thank you! :) $\endgroup$ Jan 31, 2015 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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