Combinatorial problem, (resursive functions).

[MathematicalPhysicist]

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?

 

[mmwave]

I would approach this question by breaking it down into smaller parts and using mathematical principles to find the answer.

Firstly, let's define some terms. We will call a word with n letters that contains both ACT and TTT a "valid word". We will call a word with n letters that does not contain either ACT or TTT an "invalid word".

Now, we can calculate the total number of words with n letters using the formula 4^n, as there are 4 options (A,T,G,C) for each letter in the word.

Next, we need to find the number of invalid words. To do this, we can subtract the number of valid words from the total number of words. So, our equation becomes:

Total number of words with n letters = Number of valid words + Number of invalid words

Now, let's focus on finding the number of valid words. To do this, we can use the principle of inclusion-exclusion. This principle states that to find the number of elements in a set that satisfy at least one of several conditions, we can add the number of elements that satisfy each individual condition, then subtract the number of elements that satisfy the intersection of any two conditions, then add the number of elements that satisfy the intersection of any three conditions, and so on.

In our case, we have two conditions: the word must contain ACT and the word must contain TTT. So, our equation becomes:

Number of valid words = Number of words with ACT + Number of words with TTT - Number of words with both ACT and TTT

Now, let's break down each part of this equation.

Number of words with ACT: To find this, we can fix the letters ACT in the word and then fill the remaining n-3 letters with any of the 4 options. So, there are 4^(n-3) ways to do this.

Number of words with TTT: Similarly, we can fix the letters TTT in the word and fill the remaining n-3 letters with any of the 4 options. So, there are also 4^(n-3) ways to do this.

Number of words with both ACT and TTT: To find this, we can fix the letters ACTTTT in the word and fill the remaining n-6 letters with any of the 4 options. So, there are 4^(n-6) ways to do this.

Now, we can

 

[tacman]

Your explanation and approach seem to be valid. The recursive formula you have derived seems to be correct, and using it to find a_n and then subtracting it from 4^n would give you the number of words with n letters that do not contain ACT or TTT. However, to find the total number of words with n letters that contain ACT or TTT, you would also need to consider the cases where these sequences appear in different positions within the word. This would require further analysis and modification of the recursive formula. Overall, your approach is a good starting point for solving this combinatorial problem.