Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorial problem, (resursive functions).

  1. Jun 15, 2007 #1


    User Avatar
    Gold Member

    my question is as follows:
    how many words with n letters, you can construct with A,T,G,C such that ACT and TTT will apear in the word?
    well i thought to count the number of the words where ACT and TTT do not appear and then substract this from 4^n.
    now if we write the number of ways to do so with a_n.
    then if the first word is either G or C then we have 2a_n-1 way to do so.
    if the the first word is either T or A then we have 2a_n-1 words, from this we substract the number of words where in the second letter and the third letter appears C or T, or T respectively, i.e we have 2a_n-2+a_n-3, i.e
    we have this recursive formula:
    a_n=2a_n-1-2a_n-2-a_n-3, where a0=1, a1=4, a2=4^2=16
    im not sure my explnantion is 100 percent valid, now i only need to find a_n (which is easy cause this a linear equation), and then substract this from 4^n.
    but is the equation correct?
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted