|
%I #46 Mar 02 2024 12:33:18
%S 0,0,1,5,21,79,281,963,3217,10547,34089,108955,345137,1085331,3392377,
%T 10549739,32667201,100782787,309946697,950599131,2908512145,
%U 8880484019,27064776729,82350874699,250212362465,759269653155,2301393567721,6968615051195
%N Number of ternary strings of length n containing 00.
%H G. C. Greubel, <a href="/A186244/b186244.txt">Table of n, a(n) for n = 0..1000</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (5,-4,-6).
%F a(n) = 3*a(n-1) + 2*(3^(n-3) - a(n-3)). This recursive formula is based on adding any of {0,1,2} to strings of length n-1 which already have 00 in them, or {100,200} to strings of length n-3 which do not. For n = 3, we add {0,1,2} to 00, and {100,200} to the empty string to get the 5 strings of length 3 which have 00 in them. For n = 4, we add {0,1,2} to those 5, and {100,200} to all three strings of length 1, to get the 21 strings of length 4.
%F a(n) = -(1/3)*(1+sqrt(3))^n*sqrt(3) - (1/2)*(1+sqrt(3))^n + 3^n - (1/2)*(1-sqrt(3))^n + (1/3)*sqrt(3)*(1-sqrt(3))^n. - _Alexander R. Povolotsky_, Feb 18 2011
%F G.f.: x^2/(3*x-1)/(2*x^2+2*x-1). - _Simon Plouffe_, Feb 26 2011
%F a(n) = 3^n - A028859(n). - _Toby Gottfried_, Mar 06 2013
%F a(n) = 2*a(n-1) + 2*a(n-2) + 3^(n-2). This recursive formula is based on adding the case where the last two digits are not the same to the case where the last two digits are the same. In the first case, there are 2*a(n-1) strings, since any string of length n-1 containing 00 can be made into an appropriate string of length n by appending either of the values {0,1,2} that are not the same as the (n-1)-th digit. The case where the last two digits are the same has two subcases: to any string of length n-2 containing 00, we can append 11 or 22. There are 2*a(n-2) strings in this subcase. Or, to any string of length n-2 (whether or not it contains 00), we can append 00. There are 3^(n-2) strings in this subcase. - _Todd CadwalladerOlsker_, Oct 24 2020
%F a(n) = 5*a(n-1) - 4*a(n-2) - 6*a(n-3). - _Kevin Ryde_, Oct 24 2020
%F E.g.f.: exp(x)*(exp(2*x) - cosh(sqrt(3)*x) - 2*sinh(sqrt(3)*x)/sqrt(3)). - _Stefano Spezia_, Mar 02 2024
%t t = {0, 0, 1}; Do[AppendTo[t, 3 t[[-1]] + 2*(3^(n - 3) - t[[-3]])], {n, 3, 40}]; t (* _T. D. Noe_, Nov 11 2013 *)
%t CoefficientList[Series[x^2/(3*x - 1)/(2*x^2 + 2*x - 1), {x,0,50}], x] (* _G. C. Greubel_, Feb 19 2017 *)
%o (PARI) x='x+O('x^50); Vec(x^2/(3*x - 1)/(2*x^2 + 2*x - 1)) \\ _G. C. Greubel_, Feb 19 2017
%o (PARI) a(n)=3^n - ([1, 3; 1, 1]^n*[2; 1])[2, 1] \\ _Charles R Greathouse IV_, Feb 19 2017
%Y Cf. A028859, A186314 (number of ternary strings of length n containing 01), A351529 (4-ary), A351530 (5-ary).
%K easy,nonn
%O 0,4
%A _Toby Gottfried_, Feb 15 2011
|
