A186244 Number of ternary strings of length n containing 00.

0, 0, 1, 5, 21, 79, 281, 963, 3217, 10547, 34089, 108955, 345137, 1085331, 3392377, 10549739, 32667201, 100782787, 309946697, 950599131, 2908512145, 8880484019, 27064776729, 82350874699, 250212362465, 759269653155, 2301393567721, 6968615051195

Offset

0,4

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (5,-4,-6).

Formula

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.

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

G.f.: x^2/(3*x-1)/(2*x^2+2*x-1). - Simon Plouffe, Feb 26 2011

a(n) = 3^n - A028859(n). - Toby Gottfried, Mar 06 2013

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

a(n) = 5*a(n-1) - 4*a(n-2) - 6*a(n-3). - Kevin Ryde, Oct 24 2020

E.g.f.: exp(x)*(exp(2*x) - cosh(sqrt(3)*x) - 2*sinh(sqrt(3)*x)/sqrt(3)). - Stefano Spezia, Mar 02 2024

Mathematica

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 *)
CoefficientList[Series[x^2/(3*x - 1)/(2*x^2 + 2*x - 1), {x, 0, 50}], x] (* G. C. Greubel, Feb 19 2017 *)

Prog

(PARI) x='x+O('x^50); Vec(x^2/(3*x - 1)/(2*x^2 + 2*x - 1)) \\ G. C. Greubel, Feb 19 2017
(PARI) a(n)=3^n - ([1, 3; 1, 1]^n*[2; 1])[2, 1] \\ Charles R Greathouse IV, Feb 19 2017

Crossrefs

Cf. A028859, A186314 (number of ternary strings of length n containing 01), A351529 (4-ary), A351530 (5-ary).

Sequence in context: A108863 A027172 A244198 * A255447 A029870 A269915

Adjacent sequences: A186241 A186242 A186243 * A186245 A186246 A186247

Keyword

easy,nonn

Author

Toby Gottfried, Feb 15 2011

Status

approved