# Am i understanidng this right, counting strings

1. Nov 21, 2006

### mr_coffee

Hello everyone. I'm not sure if i'm doing this right or not. The problem asks:

Consdier the set of all strings of a's, b's, and c's.

a. make a list of all of these strings of lengths zero, one, two, and three that do not contain the pattern aa.

Okay so i have the following:
note e: stands for empty
length 0: e
length 1: a; b; c;
length 2: {a,b}, {a,c}, {b,c}, {b,b}, {c,c}
okay for lenght 2, i'm confused, do they want all possibe like for instance:
is {a,b} equal to {b,a}? like {1,2} would be equal to {2,1} if we are just talking about sets, order doesn't matter but i'm not sure if they are talking about sets or not...

Length 3: {aba, abb, abc, aca, acb, acc, bab, bac,
bba, bbb, bbc, bca, bcb, bcc, bcab, cac, cba, cbb, cbc,
cca, ccb, ccc}

its also asking in part b:
For each integer n >= 0, let S_n = the number of strings of a's, b'c, and c's of length n that do not contain the pattern aa. Find S_O, S_1, S_2, and S_3

So would S_O = 1; S_1 = 3; S_2 = 5 or would string of length 2, that do not contain aa be more?
length 2: {a,b}, {a,c}, {b,c}, {b,b}, {c,c}
like: length 2: ab,ba,ac,ca,bc,cb,bb,cc
so S_2 = 8
and is S_3 = 22?

find a recurrence rleation for s_0, S_1, S_2......
and the answer is: $$s_{k} = 2*s_{k-1} + 2*s_{k-2}$$

and for part D:

they are saying to use part b and c to find the number of strings of a's , b's, and c's of length four that do not contian the pattern aa.
But I thought I just foudn this in part a and b didn't i?

Thanks!

Last edited: Nov 21, 2006
2. Nov 22, 2006

### mr_coffee

n/m i got it:
s_4 = 60

and i shouldn't treat them as sets, {a,b} ! = {b,a} in this case