|
%I #19 Apr 07 2020 23:15:53
%S 1,3,9,27,79,229,657,1871,5295,14909,41801,116783,325287,903741,
%T 2505377,6932479,19151519,52833853,145578265,400705135,1101936119,
%U 3027902045,8314284721,22816209855,62579270191,171559358493,470132335209,1287861941487,3526800739399
%N Number of length-n ternary strings that do not contain both "00" and "11".
%H Colin Barker, <a href="/A282087/b282087.txt">Table of n, a(n) for n = 0..1000</a>
%H Math StackExchange, <a href="http://math.stackexchange.com/questions/2128688/find-a-recurrence-relation-for-the-number-of-ternary-strings-of-length-%DD%8A-that-do/2129218#2129218">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</a>.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-1,-6,-2).
%F 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).
%F From _Colin Barker_, Feb 07 2017: (Start)
%F 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).
%F G.f.: (1 + x)*(1 - 2*x) / ((1 - 2*x - x^2)*(1 - 2*x - 2*x^2)).
%F (End)
%e 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'.
%t Table[3^n, {n, 0, 3}]~Join~LinearRecurrence[{4, -1, -6, -2}, {79, 229, 657, 1871}, 24] (* or *)
%t 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 *)
%o (Python)
%o import itertools
%o # Not feasible on most machines for large numbers
%o def find_a_sub_n(n):
%o c = 0
%o for q in itertools.product(*([['0','1','2']]*n)):
%o h = ''.join(q)
%o if not (('11' in h) and ('00' in h)):
%o c = c+1
%o return c
%o (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
%o (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
%Y Cf. A078057 (number of length-n ternary strings that contain neither "00" nor "11").
%K nonn,easy
%O 0,2
%A _Daniel T. Martin_, Feb 05 2017
|
