retagged by
3,643 views
3 votes
3 votes
If $a_n$ is number of ternary sequences of length $n$ with even number of $0$'s, then the recurrence relation for $a_n$ is?

Also find the value of $a_8$.
retagged by

3 Answers

Best answer
3 votes
3 votes

$a_{n} =$  No of ternary string containing even no of zeros.

$= 2 \times a_{n-1} + (3 ^{n-1}  - a_{n-1} )$

$= a_{n-1} + 3^{n-1}$

                
The last symbol that is $n^{th}$ symbol may be 1 or 2 and this wont effect the even no of zeros which will also be present in the string of size $a_{n-1}$ .  Therefore twice of $a_{n-1}$ is used.

Now, if the $n^{th}$ symbol is 0 we can count all strings with "odd" number of 0's of length $n-1$ which is given by $a_{n-1}' = 3^{n-1} - a_{n-1}$.
 

Let $a_{0}  = 1$
$a_{1} = 2$  because {1, 2} have 0 no of zeros which are valid.
$a_{2}  = a_1 + 3^1 = 5$  the possible 2 length string with even no of zeros {00,11,12,21,22}
$a_{3} = a_2 + 3^2 = 14$
$a_{4} = a_3 + 3^3 = 41$
$a_5 = a_4 + 3^4 = 122$
$a_6 = a_5 + 3^5 = 365$
$a_7 = a_6 + 3^6 = 1094$
$a_8 = a_7 +3^6 = 3281$.

 

selected by
3 votes
3 votes

Let T(n) be a number of ternary strings of length 'n'.

now, we have 3 choices- these strings can end with either 0  or 1 or 2.

case 1: Ending with 1

T(n) is the number of strings having an even number of zeroes and ending with 1 only if in rest (n-1) bits has even number of zeroes.

so we have T(n-1) such strings having an even number of zeroes and ending with 1.

case 2:: Ending with 2

T(n) is the number of strings having an even number of zeroes and ending with 2 only if in rest (n-1) bits has even number of zeroes.

so again we have T(n-1) such strings ending with 2 and having an even number of zeroes.

Case 3: Ending with 0.

Now, if last bit is 0, then to make it a string containing even numbered zeroes, we should have odd numbers of zeroes in rest n-1 bits.

T(n) is the number of n bit strings with even zeroes but now what we want is the number of strings of length n-1 having 'odd numbers of zeroes', which is nothing but the complement of our T(n)

we can calculate it as follows:

number of strings of length n-1 having odd zeroes= total strings possible with n-1 bits- strings of length n-1 with even zeroes

                                                                                 = 3(n-1) - T(n-1)

 

so T(n)= T(n-1) + T(n-1) + 3(n-1) - T(n-1)

     T(n)    = T(n-1) + 3(n-1)

 

 

 

 

1 votes
1 votes

For ternary sequence symbols are 0 1 2

an represents sequence of length n

We want even no of 0

case 1:So lets say if last digit of sequence is 1 or 2 we need to look in sequence an-1for even no of zeros

case 2 if last digit is 0 so to have even no of zeros there must odd no of zeros in an-1

so recurrence equation is

an=2an-1+(3n-1-an-1)

      =an-1+3n-1

for a8 substitute n=8

Related questions

1 votes
1 votes
0 answers
2
Jason asked Apr 12, 2018
609 views
Given symbols:- $GGGGGAAATTTECCS$No of ways such that exactly 4 Gs out of 5 Gs are together. I am getting$ \frac{11! × 11}{3!×3!×2!} $.Some one verify it?
1 votes
1 votes
1 answer
3
sripo asked Nov 14, 2018
1,573 views
T(n)=T(n/2)+2; T(1)=1when n is power of 2 the correct expression for T(n) is:a) 2(logn+1)b) 2lognc)logn+1d)2logn+1
0 votes
0 votes
2 answers
4