How many of the strings of ten characters over the alphabet {a,b} contain the substring aba?

combinatorics/aba.strings New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

How many of the strings of ten characters over the alphabet {a,b}
contain the substring aba?  More generally, how many of the strings of
length N over a K-character alphabet contain a given substring w?

> Here's a problem which we were going to put on the first year
> combinatorics exam, but much to our surprise it turned out to be far
> too complicated:
>
> How many of the strings of ten characters using the two character
> alphabet { a,b } contain the sub-string aba?
>
> If you can answer the previous question (and I can't) why not try
> the more general question: how many of the strings of length N using
> a K character alphabet contain the substring w?

-- <finlowk@vax.sbu.ac.uk>, "aba string problem", April 1995

Show solution

It's not that complicated.  I'm not sure your students should be able
to get it under the time pressure of an exam, but I'm surprised you
didn't get it when you set out to post about it.

Let's count the number of strings of various lengths _lacking_ the
substring "aba", forming a recurrence by counting the ways of adding a
new letter to the end of the previous strings.  In order to avoid
generating strings ending in "aba", we must keep a separate count of
strings ending in "ab", and in order to count those, we must also keep
a count of strings ending in "a".

So of the abaless strings of length n, let us suppose there are Nab(n)
ending in "ab", Na(n) ending in "a", and Nx(n) others.  Immediately,

    Nab(0)=Na(0)=0, Nx(0)=1,

    Nab(n+1)=Na(n),
     Na(n+1)=Na(n)+Nx(n)   (Remember not to add an "a" to the Nab(n)),
     Nx(n+1)=Nx(n)+Nab(n).

It's easy enough to use this recurrence to make up a table of Nab(n),
Na(n), Nx(n) for n=0,...,10, but there is a better way.  Representing
the recurrence by a matrix, we have

                             [ 0  0  1 ]
    [ Nab(n), Na(n), Nx(n) ] [ 1  1  0 ] = [ Nab(n+1), Na(n+1), Nx(n+1) ]
                             [ 0  1  1 ]

If we name the matrix A, we need to compute A^10:

                  [ 0 1 1 ]                        [ 2 3 2 ]
      A^2 = A A = [ 1 1 1 ];       A^4 = A^2 A^2 = [ 2 4 3 ];
                  [ 1 2 1 ]                        [ 3 5 4 ]

                  [ 3 5 4 ]                   [ 49  86  65 ]
    A^5 = A^4 A = [ 4 7 5 ]; A^10 = A^5 A^5 = [ 65 114  86 ];
                  [ 5 9 7 ]                   [ 86 151 114 ]


    [ Nab(10), Na(10), Nx(10) ] = [ Nab(0), Na(0), Nx(0) ] A^10
                                = [ 0, 0, 1 ] A^10
                                = [ 86, 151, 114 ].

[ Editor: the original has "Nab(0)" for "Nx(0)" in the first line;
the next line uses [ 0, 0, 1 ], i.e. Nx(0) = 1. ]

So the answer is 2^10 - 86 - 151 - 114 = 673.

> how many of the strings of length N using a K character alphabet
> contain the substring w?

The same method works.

ObPuzzles: 1. Why are there only five distinct values in A^n?
           2. What limits do Na(n)/Nab(n) and Na(n)/Nx(n) approach?
           3. Will generating functions yield a closed form for these
              functions?

-- Dan Hoey <Hoey@AIC.NRL.Navy.Mil>