Recursion question I think?

5

5ugxr

New member
Joined
Jul 9, 2024
Messages
36
Determine the number of eight-letter strings of As, Bs, and Cs with the property that every C in the string is next to another C. For example, ABCBACBC should not be counted, but ABBCCAAB and CCCBACCB should.

I'm not quite sure where to start. I've tried using cases where there's 0 to 8 C's but it starts to get really extensive.. some people have told me to try getting a recursion formula but I don't know how to create one for this kind of question...

Question is from a Problem Solving course so there must be some intuitive way to solve this but I'm not seeing it
 
If you have the final answer, we might be able find a pattern to get it.
 
5ugxr said:
Determine the number of eight-letter strings of As, Bs, and Cs with the property that every C in the string is next to another C. For example, ABCBACBC should not be counted, but ABBCCAAB and CCCBACCB should.

I'm not quite sure where to start. I've tried using cases where there's 0 to 8 C's but it starts to get really extensive.. some people have told me to try getting a recursion formula but I don't know how to create one for this kind of question...

Question is from a Problem Solving course so there must be some intuitive way to solve this but I'm not seeing it
Click to expand...
Instead of counting the number of valid strings, it might be easier to count the total number of strings and subtract the number of invalid strings.
 
lev888 said:
Instead of counting the number of valid strings, it might be easier to count the total number of strings and subtract the number of invalid strings.
Click to expand...
Yes I think that also works, I think the total is 3^8 strings., but I am not sure how to count the number of invalid strings.

Just thinking out loud,
An invalid case means there must be at least one C that is alone. Lets let D be either A or B, and X to be either A, B, or C.
Our C can never have an X beside it and should have a D
E.g CDXXXXXX
DCDXXXXX
XDCDXXXX
XXDCDXXX
XXXDCDXX
XXXXDCDX
XXXXXDCD
XXXXXXDC

For each X there are 3 possibilities and each D has 2 possibilities
So we can find the total sequences from these cases by multiplying
We get the numbers
2 * 3^6 =1458
(2^2) * (3^5) = 972
(2^2) * (3^5) = 972
(2^2) * (3^5) = 972
(2^2) * (3^5) = 972
(2^2) * (3^5) = 972
(2^2) * (3^5) = 972
2 * 3^6 = 1458

However the sum will give us 8748, which is greater than the total of 3^8 = 6561. I thought I was onto something haha but looks like there is an error somewhere. Can anyone see it? (Maybe my whole approach is wrong :> I just woke up)
 
Actually I notice I am counting some cases multiple times.
E.g for XDCDXXXX and XXXDCDXX
AACACAAA and other cases also work but I count them multiple times. Im not sure how I can fix this or if it can be fixed
 
5ugxr said:
Determine the number of eight-letter strings of As, Bs, and Cs with the property that every C in the string is next to another C. For example, ABCBACBC should not be counted, but ABBCCAAB and CCCBACCB should.

I'm not quite sure where to start. I've tried using cases where there's 0 to 8 C's but it starts to get really extensive.. some people have told me to try getting a recursion formula but I don't know how to create one for this kind of question...

Question is from a Problem Solving course so there must be some intuitive way to solve this but I'm not seeing it
Click to expand...
Should the strings with no C's be counted? E.g. AAAAAAAA ?
 
5ugxr said:
Actually I notice I am counting some cases multiple times.
E.g for XDCDXXXX and XXXDCDXX
AACACAAA and other cases also work but I count them multiple times. Im not sure how I can fix this or if it can be fixed
Click to expand...
Try to organize counting of invalid strings in a different way, so that the cases don't intersect. E.g. each case has different number of Cs.
 
Im not sure how I can make each case have a different number of C's.

Im wondering if this works:

Say I have
Case 1: CDXXXXXX
Case 2: XDCDXXXX
Case 3: XXXDCDXX
Case 4: XXXXXDCD

Each of these cases have duplicates of another case because in each case where there is a C, another case has an X. Since an X can be A, B, or C, if X is C in that position then its a duplicate case. So, we should change X to be D in that position.
Case 1: CDXXXXXX
Case 2: DDCDXXXX
Case 3: DXXDCDXX
Case 4: DXXXXDCD

I changed each X in the first position to be D so it cannot overlap with Case 1
Now Case 1 must be unique
However case 2,3,4 can still be duplicates because in Case 2 third position there is a C, while in Case 3 and 4 there are X's which can also be C's. So we should change them to be D.

Case 1: CDXXXXXX
Case 2: DDCDXXXX
Case 3: DXDDCDXX
Case 4: DXDXDDCD

This leaves me with these 4 cases.
I can do the same with the other 4 cases where ill call them Case A,B,C,D

Case A: DCDXXXXX
Case B: XXDCDXXX
Case C: XXXXDCDX
Case D: XXXXXXDC

Changes to:
Case A: DCDXXXXX
Case B: XDDCDXXX
Case C: XDXDDCDX
Case D: XDXDXDDC

In summary , for each case if a C appeared then that means in another case the C can't appear again so it must be A or B is essentially what I did(?)

The final cases are:
Case 1: CDXXXXXX
Case 2: DDCDXXXX
Case 3: DXDDCDXX
Case 4: DXDXDDCD

Case A: DCDXXXXX
Case B: XDDCDXXX
Case C: XDXDDCDX
Case D: XDXDXDDC

The calculation is:
2 * (3^6) = 1458
(2^3) * (3^4) = 648
(2^4) * (3^3) = 432
(2^4) * (3^3) = 432
(2^2) * (3^5) = 972
(2^3) * (3^4) = 648
(2^4) * (3^3) = 432
(2^4) * (3^3) = 432

Summing this up, we get 5454

6561 - 5454 = 1107

Therefore there are 1107 valid cases... could you see if this seems right?
 
I'd try to come up with a formula for the number of ways to place non-adjacent C's. This might benefit from recursion.
 
blamocur said:
I'd try to come up with a formula for the number of ways to place non-adjacent C's. This might benefit from recursion.
Click to expand...
Im not really sure how to create a recursion formula, I just learned the basics a few days ago... I feel like it with all the A's, B's and C's the recursion might be over the level of the course I'm taking (gr11/12). I messaged my instructors regarding my method and am awaiting a response.
Do my previous steps make sense? Might have some mistakes, never had any kind of questions like this in day school 😅
 
5ugxr said:
Therefore there are 1107 valid cases... could you see if this seems right?
Click to expand...
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?
 
5ugxr said:
Im not really sure how to create a recursion formula,
Click to expand...
If [imath]A_{k,n}[/imath] is the number of ways to place [imath]k[/imath] non-adjacent C's in [imath]n[/imath] positions you can express it through [imath]A_{k-1,j}[/imath]'s where [imath]j<n[/imath].
 
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...
The numbers tell me how many strings there are for each case

For example Case 1 I said it was CDXXXXXX
Where D can be A or B, and X can be A, B, or C
Since D has 2 options: to be A or B, and similarly X has 3 options (A, B, or C)
So I multiply them to find all combinations that satisfy CDXXXXXX

Example if I have a 3 letter combination that can only use A or B that means I have 2 options for each letter
I multiply them 2 x 2 x 2 = 8 possible combinations
(AAA, BBB, ABA, BAB, BBA, AAB, ABB, BAA)
 
mario99 said:
What is your idea here for not letting [imath]D = C[/imath]?
Click to expand...
Because if D can be C then for some strings it will be valid since C is not alone. I need there to be at least one C that is isolated and I guess limiting D to A or B does that (hopefully)
 
5ugxr said:
Because if D can be C then for some strings it will be valid since C is not alone. I need there to be at least one C that is isolated and I guess limiting D to A or B does that (hopefully)
Click to expand...
Ok, I got your idea.
 
5ugxr said:
Because if D can be C then for some strings it will be valid since C is not alone. I need there to be at least one C that is isolated and I guess limiting D to A or B does that (hopefully)
Click to expand...
I like your idea here. Now, I got an idea based on your idea.

Reduce the eight-letter string to three-letter or four-letter string. Apply your idea. When you finish, increase the string by one letter and apply the idea again. With this, you will see pattern that will create a formula for a general case. Then you can even apply it for a 1000-letter string.
 
mario99 said:
I like your idea here. Now, I got an idea based on your idea.

Reduce the eight-letter string to three-letter or four-letter string. Apply your idea. When you finish, increase the string by one letter and apply the idea again. With this, you will see pattern that will create a formula for a general case. Then you can even apply it for a 1000-letter string.
Click to expand...
Ok

3 letters
3^3 = 27 is total
CDX 2*3 = 6
DCD 2*2 = 4
DDC 2*2 = 4
6+4+4=14
27-14 = 13

4 letters
3^4 = 81 is total
CDXX 2*3*3 = 18
DCDX 2*2*3 = 12
DDCD 2*2*2 = 8
DDDC 2*2*2 = 8
18+12+8+8=46
81-46 = 35

5 letters
3^5 = 243
CDXXX 2*3*3*3=54
DCDXX 2*2*3*3=36
DDCDX 2*2*2*3=24
DDDCD 2^4 = 16
DDDDC 2^4 = 16
54+36+24+16+16 = 146
243-146 = 97

I have 13, 35, and 97 for 3,4, and 5 letters

Im not seeing a pattern yet ill try it for 2 letters
3^2 = 9
CD = 2
DC = 2
9 - 2 - 2 = 5
for 2,3,4,5 letters we get 5,13,35,97

also I noticed that the solution I proposed before is wrong I am still missing some duplicate cases. it looks like for all X under C I need to make it D so ill retry it
 
You must log in or register to reply here.
Top