Recursion question I think?

The new cases I am getting are:

Case 1: CDXXXXXX

Case A: DCDXXXXX

Case 2: DDCDXXXX

Case B: DDDCDXXX

Case 3: DDDDCDXX

Case C: DDDDDCDX

Case 4: DDDDDDCD

Case D: DDDDDDDC

Where D can be A or B. and X can be A, B, or C. So, D has 2 possibilities and X has 3 possibilities. We can find the total strings by the following calculations:

2*(3^6) = 1458
(2^2)*(3^5) = 972
(2^3)*(3^4) = 648
(2^4)*(3^3) = 432
(2^5)*(3^2) = 288
(2^6)*3 = 192
(2^6)*3 = 192

Summing them up this time we get:
1458+972+648+432+288+192+192 = 4182

6561 - 4182 = 2379
We get 2379 valid strings this time.
 
f(n) = 2^n + 3^n
This is the pattern rule Wolframalpha gave me for 2,5,13,35,97,275 which are the strings for 1 to 6 digits . So it turns out it wasn't a recursion question I guess... But still Im not sure how we get this. I have to explain my answer to my teacher so how would I show my work?
 
f(n) = 2^n + 3^n where the 8 letter string is when n = 7
So what would be more correct is
f(n) = 2^(n-1) + 3^(n-1)
 
Last edited:
Im confused again... for length 4 someone told me they only got 33 possibilities.
they calculated only the valid strings
DDDD
CCDD
DCCD
DDCC
CCCD
DCCC
CCCC

Problem is I don't see how its wrong so now I'm second guessing myself
 
blamocur said:
No, this answer is not right. I don't understand your reasoning in post # 10: you looks at some special cases, then list a bunch of numbers in the end. Where do those numbers come from?
Click to expand...
Actually, I am not sure. The number I got on my computer at the time of my previous post is wrong: I calculated all cases where every C is isolated.
 
blamocur said:
Actually, I am not sure. The number I got on my computer at the time of my previous post is wrong: I calculated all cases where every C is isolated.
Click to expand...
I got [imath]3280[/imath] ways of isolated C's based on a pattern depends on 2-letter and 3-letter strings!

This is why I asked for the final solution, so that we can compare our answers with it. If we are wrong we can improve it more.
 
5ugxr said:
f(n) = 2^n + 3^n
This is the pattern rule Wolframalpha gave me for 2,5,13,35,97,275 which are the strings for 1 to 6 digits . So it turns out it wasn't a recursion question I guess... But still Im not sure how we get this. I have to explain my answer to my teacher so how would I show my work?
Click to expand...
I don't know what to say about this and your work because I don't have something to compare with!
 
mario99 said:
I got [imath]3280[/imath] ways of isolated C's based on a pattern depends on 2-letter and 3-letter strings!

This is why I asked for the final solution, so that we can compare our answers with it. If we are wrong we can improve it more.
Click to expand...
I think my previous answer is somehow also wrong... Someone got 33 strings for length 4 and for them they got a recursive formula:
a(n) = 3a(n-1)-2a(n-2)+2a(n-3)
 
mario99 said:
I don't know what to say about this and your work because I don't have something to compare with!
Click to expand...
2,5,13,33,83,209,527.. this is the pattern someone gave me

Can you see how many valid strings you get for strings of length 4? Just to make sure we are on the same page
 
blamocur said:
Actually, I am not sure. The number I got on my computer at the time of my previous post is wrong: I calculated all cases where every C is isolated.
Click to expand...
I get a number between 3000 and 3500 by subtracting arrangements with isolated C's from the total, which I think is what you are saying.
mario99 said:
I got [imath]3280[/imath] ways of isolated C's based on a pattern depends on 2-letter and 3-letter strings!

This is why I asked for the final solution, so that we can compare our answers with it. If we are wrong we can improve it more.
Click to expand...
My answer (which I haven't yet double-checked) is different.
 
Dr.Peterson said:
I get a number between 3000 and 3500 by subtracting arrangements with isolated C's from the total, which I think is what you are saying.

My answer (which I haven't yet double-checked) is different.
Click to expand...
Probably, you are the correct one professor Dave because I trust on your calculations on these type of questions!
 
Dr.Peterson said:
I get a number between 3000 and 3500 by subtracting arrangements with isolated C's from the total, which I think is what you are saying.

My answer (which I haven't yet double-checked) is different.
Click to expand...
Is it 3351?
 
Yes I included those
mario99 said:
By valid strings I meant [imath]AAAA[/imath] and [imath]ACCA[/imath] for example are included.
Click to expand...
Here is the list I tested
AAAA
AAAB
AABA"
AABB
AACC
ABAA
ABAB
ABBA
ABBB
ABCC
ACCA
ACCB
ACCC
BAAA
BAAB
BABA
BABB
BACC
BBAA
BBAB
BBBA
BBBB
BBCC
BCCA
BCCB
BCCC
CCAA
CCAB
CCBA
CCBB
CCCA
CCCB
CCCC
 
5ugxr said:
Yes I included those

Here is the list I tested
AAAA
AAAB
AABA"
AABB
AACC
ABAA
ABAB
ABBA
ABBB
ABCC
ACCA
ACCB
ACCC
BAAA
BAAB
BABA
BABB
BACC
BBAA
BBAB
BBBA
BBBB
BBCC
BCCA
BCCB
BCCC
CCAA
CCAB
CCBA
CCBB
CCCA
CCCB
CCCC
Click to expand...
This means that there are [imath]81 - 33 = 48[/imath] invalid strings while my not well developed formula gives me [imath]40[/imath]. I am wondering if professor Dave has the same result as this!
 
mario99 said:
This means that there are [imath]81 - 33 = 48[/imath] invalid strings while my not well developed formula gives me [imath]40[/imath]. I am wondering if professor Dave has the same result as this!
Click to expand...
I also get 33 valid strings.

I think I found a way to use recursion. Not super elegant, but good enough to allow computing the answer by hand. Using the same notation as @5ugxr used in post #5 we can break all sequences of length [imath]n[/imath] into the following classes (each class starts with 0 or 2+ C's followed by D followed by a good string of smaller length, and the class is named according to the position of the first non-C):

Class 0DX..XFirst non-C at position 0, the rest of the string is good.
Class 2CCDX...XFirst non-C at position 2, the rest of the string is good.
Class 3CCCDX..X
Class 4CCCCDX...X
...........
Class [imath]n-1[/imath]CCC...CDAll C's except the last
Class [imath]n[/imath]CCC...CAll C's

In each class the X's following D must form a good sequence. This means that the number [imath]F_n[/imath] of good classes of length [imath]n[/imath] can be expressed through [imath]F_k[/imath] for [imath]k<n[/imath]. I still could not find a nice expression for [imath]F_n[/imath], but I could compute [imath]F_8[/imath] using recursion.
 
Someone on discord found the recursive formula a(n) = 3a(n-1)-2a(n-2)+2a(n-3)
Their explaination was:

take all the valid strings of length n-1 and append an A,B or C at the end in 3a(n-1) ways.the ones ending in A,B are valid, but some of the ones ending in C aren't, namely when the (n-1)-st digit is A or B. there are 2a(n-2) of these, since to construct them, you start with a valid string of length n-2 and append AC or BC at the end. moreover, there are those valid strings ending in ACC or BCC which are not obtained in the preceding way (the first n-1 digits of these strings are not themselves valid), and there are 2a(n-3) of these (edited)

wondering if the reasoning is right
 
You must log in or register to reply here.
Top