login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A186244 Number of ternary strings of length n containing 00. 5
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

LINKS

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

FORMULA

a(n) = 3*a(n-1) + 2*(3^(n-3) - a(n-3))

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

EXAMPLE

The 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.

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. A186314 (number of ternary strings of length n containing 01).

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 1 04:57 EDT 2020. Contains 334758 sequences. (Running on oeis4.)