1

At the start , I have word of length N(N characters in a word) And each character can only be A,B or C

Now the words that i want is words that have 3 or more same character that is next to each other.

Example N=4

Want: AAAB,BBBB,ACCC........ Don't want: AABC CACC...

Now I want to know how many words do I want in the length N

Example

N=3, I will only want 3 words , AAA,BBB,CCC

As far as I can think of is to use ternary numeral system. But haven't got any Ideas yet.

Can you guys kindly help me to figure out the idea to solve this problem. Thank you.

---EDIT!! I found this set of number that I can use , but I have no idea how they are relate to each other , if you can, please provide me answer :)

3, 15, 63, 237, 843, 2889, 9651.......

Poomrokc The 3years
  • 135

2 Answers2

2

It will be much simpler to describe words with two or less repeated characters. Those can be constructed inductively:

Let $A_n$ denote the number of words of length $n$ ending with two different characters and let $B_n$ denote the number of words of length $n$ ending with two identical characters. Then we must have $$ \begin{align} A_{n+1}&=2(A_n+B_n)\\ B_{n+1}&=A_n \end{align} $$ Since $B_n=A_{n-1}$, these can be combined to the recurrence relation $$ A_{n+1}=2(A_n+A_{n-1}) $$ Then note that $A_1=3$ and $A_2=6$. This recurrence can be solved to obtain $$ A_n=\frac{\sqrt 3\left((1+\sqrt 3)^n-(1-\sqrt 3)^n\right)}2 $$ This produces a list starting with 3, 6, 18, 48, 132, 360, 984, 2688, 7344, 20064, 54816, 149760, 409152, 1117824, 3053952, 8343552, 22795008, 62277120, 170144256, 464842752.

Now we are able to give a closed form expression for the number $C_n$ of words of length $n$ having at most two consecutive repetitions of a letter, namely: $$ C_n=A_n+B_n=A_n+A_{n-1} $$ and from that we easily get the number $D_n$ of words of length $n$ having at least three consecutive repetition of some letter: $$ D_n=3^n-C_n=3^n-(A_n+A_{n-1}) $$

Based on this we should have: $$ \begin{align} D_2&=3^2-(6+3)&&=0\\ D_3&=3^3-(18+6)&&=3\\ D_4&=3^4-(48+18)&&=15\\ D_5&=3^5-(132+48)&&=63\\ &\vdots\\ D_{20}&=3^{20}-(464842752+170144256)&&=2851797393 \end{align} $$ and so on. The values of $D_3,...,D_{20}$ form the list:

3, 15, 63, 237, 843, 2889, 9651, 31641, 102267, 326865, 1035411, 3255993, 10177131, 31649217, 98001603, 302348361, 929840091, 2851797393

String
  • 18,395
1

I can't add to String's superb answer in any meaningful way except to say that it might be useful to clarify that $B_{n}$ is the number of strings ending in 2 identical characters but not 3 or more.

Otherwise it would be the case that:

$B_{n+1} = A_{n} + B_{n}$

Then later to say that $A_{2} = 6$ and since $B_{2} = 3$ to formally set $A_{1} = 3$

Michael E
  • 494
  • Indeed! That is a reasonable clarification to make. BTW $A_1=3$ just reflects that you have $A,B$ and $C$ as words of length $n=1$ not ending with two identical characters. – String Mar 06 '15 at 13:33