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
    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?
Draft saved Draft deleted



Similar Discussions: Combinatorial problem, (resursive functions).
  1. Combinatorial Problem (Replies: 1)

Loading...