A282087 Number of length-n ternary strings that do not contain both "00" and "11".

1, 3, 9, 27, 79, 229, 657, 1871, 5295, 14909, 41801, 116783, 325287, 903741, 2505377, 6932479, 19151519, 52833853, 145578265, 400705135, 1101936119, 3027902045, 8314284721, 22816209855, 62579270191, 171559358493, 470132335209, 1287861941487, 3526800739399

Offset: 0

Author

Daniel T. Martin, Feb 05 2017

Keywords

• nonn
• easy

Examples

			for n=5 the 229 acceptable ternary strings are all length 5 strings of '0', '1', and '2' _except_ '00011', '00110', '00111', '00112', '00211', '01100', '10011', '11000', '11001', '11002', '11100', '11200', '20011', '21100'.
		

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Math StackExchange, Find a recurrence relation for the number of ternary strings of length ? that do not contain two consecutive 0's and two consecutive 1's.
• Index entries for linear recurrences with constant coefficients, signature (4,-1,-6,-2).

Crossrefs

Cf. A078057 (number of length-n ternary strings that contain neither "00" nor "11").

Programs

Mathematica

Table[3^n, {n, 0, 3}]~Join~LinearRecurrence[{4, -1, -6, -2}, {79, 229, 657, 1871}, 24] (* or *)
Table[Count[Tuples[Range[0, 2], n], w_ /; Boole[SequenceCount[w, {0, 0}] > 0] Boole[SequenceCount[w, {1, 1}] > 0] == 0], {n, 0, 12}] (* Michael De Vlieger, Feb 05 2017, latter program version 10.1 *)

PARI

a(n)=([0,1,0,0;0,0,1,0;0,0,0,1;-2,-6,-1,4]^n*[1;3;9;27])[1,1] \\ Charles R Greathouse IV, Feb 05 2017

PARI

Vec((1 + x)*(1 - 2*x) / ((1 - 2*x - x^2)*(1 - 2*x - 2*x^2)) + O(x^30)) \\ Colin Barker, Feb 07 2017

Python

import itertools
# Not feasible on most machines for large numbers
def find_a_sub_n(n):
    c = 0
    for q in itertools.product(*([['0','1','2']]*n)):
        h = ''.join(q)
        if not (('11' in h) and ('00' in h)):
            c = c+1
    return c

Formula

a(n) = 4*a(n-1) - a(n-2) - 6*a(n-3) - 2*a(n-4) for n >= 4 (derived in the math.stackexchange.com link).

From Colin Barker, Feb 07 2017: (Start)

a(n) = -(1-u)^(1+n)/2 - (1+u)^(1+n)/2 + (1-v)^n - (2*(1-v)^n)/v + (1+v)^n + (2*(1+v)^n) / v where u=sqrt(2) and v=sqrt(3).

G.f.: (1 + x)*(1 - 2*x) / ((1 - 2*x - x^2)*(1 - 2*x - 2*x^2)).

(End)