1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

N letter words

  1. Feb 23, 2006 #1
    How many n-letter words can be written with A,B,C without placing two A's
    adjacent to each other?

    will this question involve some kind of genereating function....if not,,how to do it?
     
  2. jcsd
  3. Feb 23, 2006 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You can do it as a difference equation.

    Let w(n) be the number words with no repeated A's of length n.

    any such can start with a B or C and be followed by any other word of n-1 letters with no repeated As, thus

    w(n)=2w(n-1)+no. of words starting with A.

    how many words start with A? Well, the next letter can be either B or C, then there is any of the words of length n-2 with no repeated As, thus

    w(n)=2w(n-1)+2w(n-2)

    subject to the initial conditions w(1)=1, w(2)=8 (3 choices of first letter, 3 of second, minus the one double A choice).
     
  4. Feb 23, 2006 #3
    just bit more insight ...the first equation is not clear,,
     
  5. Feb 23, 2006 #4
    just bit more insight ...the first equation is not clear,,
     
  6. Feb 23, 2006 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    yes it is. think about it. I've just 'counted the possibilities'
     
  7. Feb 23, 2006 #6
    its done..Thanks Matt.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?