1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Am i understanidng this right, counting strings

  1. Nov 21, 2006 #1
    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?

    for part c its asking:
    find a recurrence rleation for s_0, S_1, S_2......
    and the answer is: [tex]s_{k} = 2*s_{k-1} + 2*s_{k-2}[/tex]

    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?

    Last edited: Nov 21, 2006
  2. jcsd
  3. Nov 22, 2006 #2
    n/m i got it:
    s_4 = 60

    and i shouldn't treat them as sets, {a,b} ! = {b,a} in this case
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook