From dawagner@flagstaff.princeton.edu Sun Feb 12 01:27:52 EST 1995
Article: 82480 of sci.math
Newsgroups: sci.math
Path: princeton!flagstaff.princeton.edu!dawagner
From: dawagner@flagstaff.princeton.edu (David A. Wagner)
Subject: Re: Simple (?) combinatoric question
Message-ID: <1995Feb12.033018.15436@Princeton.EDU>
Originator: news@hedgehog.Princeton.EDU
Sender: news@Princeton.EDU (USENET News System)
Nntp-Posting-Host: flagstaff.princeton.edu
Cc: mcovingt@ai.uga.edu
Organization: Princeton University
References: <3hjl1n$1u2@hobbes.cc.uga.edu>
Date: Sun, 12 Feb 1995 03:30:18 GMT
Lines: 32

In article <3hjl1n$1u2@hobbes.cc.uga.edu>,
Michael Covington <mcovingt@ai.uga.edu> 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                                             dawagner@princeton.edu