A ternary string is a string that is composed of at most three different symbols. 021102 is a ternary string over {0, 1, 2}, and acbabbc is a ternary string over {a, b, c}.
How many strings of length n contain consecutive symbols that are the same?
Examples: abcabc does not qualify, because there are no repeated letters. abccba does, because c repeats itself consecutively.
2007-01-02 13:00:01 · 6 answers · asked by Jim Burnell 6 in Science & Mathematics ➔ Mathematics
I mean at least one pair.
2007-01-02 13:04:03 · update #1
Just to make it more clear, I am looking for the number of ternary strings of at length n which contain AT LEAST one instance of a repeated symbol.
2007-01-02 13:05:51 · update #2
I'll begin by determining how many ternary strings of length n *don't* contain consecutive symbols. I'll use induction:
length 1: 3 strings
length 2: 3*2 strings (each length 1 string has 2 possible suffixes that work)
length 3: 3*2*2 strings (2 suffixes for each length 2 string)
...
length n: 3 * (2^(n-1)) strings
The total number of length n ternary strings is 3^n. So the number containing consecutive symbols that are the same is
3^n - (3 * (2^(n-1))
2007-01-02 13:16:42 · answer #1 · answered by zak_track 3 · 1⤊ 0⤋
This Site Might Help You.
RE:
How many ternary strings of length n contain two consecutive symbols that are the same?
A ternary string is a string that is composed of at most three different symbols. 021102 is a ternary string over {0, 1, 2}, and acbabbc is a ternary string over {a, b, c}.
How many strings of length n contain consecutive symbols that are the same?
Examples: abcabc does not qualify, because...
2015-08-18 17:32:49 · answer #2 · answered by Sergio 1 · 0⤊ 0⤋
Ternary String
2016-10-17 22:24:27 · answer #3 · answered by ? 4 · 0⤊ 0⤋
Number of strings you want+Number of strings you don't want=all strings
therefore,
Number of strings you want=all strings-number of strings you don't want.
to find the number of all strings, there are 3 choices for the first symbol, 3 for the second, etc. so it's 3*3*3*...*3=3^n.
to find the number of strings you don't want, think of it this way, the first symbol could be anything, so that's 3 possibilities. For each of those choices of the first one, there are 2 other symbols that the second symbol could be. For each of those choices of the second one, there's 2 new choices for the third symbol (to make it different from the preceding symbol) etc. Therefore it's 3*2*2*2*...*2=3*2^(n-1)
Therefore, the number you want is 3^n-3*2^(n-1)
2007-01-02 13:31:02 · answer #4 · answered by Anonymous · 1⤊ 0⤋
confusing subject. do a search onto yahoo and bing. this can assist!
2014-11-12 20:49:54 · answer #5 · answered by john 3 · 0⤊ 0⤋
countable number of strings can qualify for this.
2007-01-02 13:03:53 · answer #6 · answered by jackie 1 · 0⤊ 1⤋
Do you mean just one pair, or at least one pair?
2007-01-02 13:03:32 · answer #7 · answered by Hy 7 · 1⤊ 1⤋