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?

Improve this question
$\endgroup$
4
  • $\begingroup$ How would you handle the case of overlaps? For example, would the string $ABAB$ give a count of two? $\endgroup$
    – JRN
    Commented 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$
    – Train Heartnet
    Commented 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
    Commented Jan 30, 2015 at 13:19
  • $\begingroup$ I suppose that substring in your question means factor and not subsequence. $\endgroup$
    – J.-E. Pin
    Commented Apr 6, 2015 at 15:01

1 Answer 1

Reset to default
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}.$$

Improve this answer
$\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$
    – Train Heartnet
    Commented 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
    Commented 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$
    – Anthony Quas
    Commented 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$
    – Michael Albert
    Commented Jan 30, 2015 at 23:56
  • $\begingroup$ Oh, I understand now. Thank you! :) $\endgroup$
    – Train Heartnet
    Commented Jan 31, 2015 at 13:14

You must log in to answer this question.

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