Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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