Subject: Re: Simple (?) combinatoric question

From: [email-masked] (David A. Wagner)
Date: Sun, 12 Feb 1995 03:30:18 GMT

In article <[email-masked]>,
Michael Covington <[email-masked]> wrote:
> 
> "Given the set of strings that contain a A's, b B's, and c C's,
> how many of them contain the substring AB at least once?"
> 

Let F(a,b,c) be the desired number.  Consider the position of
the first C in any such string; then it must be preceeded by a
prefix of the form BB...BAA...A.  Let j be the number of B's in
that prefix, and k be the number of C's.  We easily obtain

F(a,b,0) = 1
F(a,b,c) = \sum_{j=0}^a \sum_{k=0}^b F(a-j,b-k,c-1).

Explicitly computing F(a,b,c) for c=0,1,2, it's natural to guess

F(a,b,c) = C(a+c,c) C(b+c,c)

where C(n,m) = n! / (m! (n-m)!) is the binomial coefficient
``n choose m''.  Verify by induction:

F(a,b,c+1) = \sum_{j=0}^a \sum_{k=0}^b C(a+c-j,c) C(b+c-k,c)
  = \sum_{j=0}^a C(a+c-j,c) \sum_{k=0}^b C(b+c-k,c)
  = C(a+c+1,c+1) C(b+c+1,c+1)

so the guess was correct.

[Nice problem, by the way!]

-------------------------------------------------------------------------------
David Wagner                                             [email-masked]