A186314 Number of ternary strings of length n which contain 01.

0, 0, 1, 6, 26, 99, 352, 1200, 3977, 12918, 41338, 130779, 410048, 1276512, 3950929, 12170598, 37343834, 114209811, 348332320, 1059927312, 3218870105, 9758944470, 29544747706, 89335651851, 269843267456, 814337329344, 2455598257057, 7399746051270

Offset

0,4

Links

Table of n, a(n) for n=0..27.

Index entries for linear recurrences with constant coefficients, signature (6,-10,3).

Formula

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

G.f.: x^2/((1-3*x)*(1-3*x+x^2)). a(n) = 3^n - A001906(n+1). - Bruno Berselli, Feb 23 2011

Example

The recursive formula is based on extending such a string of length n-1 with {0,1,2} or extending a non-matching string of length (n-2) with "01".  For n=2, there is just 1 string: "01". For n=3, we append {0,1,2} to "01" and append "01" to {"0","1","2"}, the three non-matching strings of length 1, for a total of a(3)=6.

Mathematica

nn=20; CoefficientList[Series[1/(1-3x)-1/(x^2+(1-3x)), {x, 0, nn}], x] (* Geoffrey Critzer, Dec 25 2013 *)
LinearRecurrence[{6, -10, 3}, {0, 0, 1}, 30] (* Harvey P. Dale, Jun 14 2020 *)

Crossrefs

Cf. A186244 (ternary strings which contain 00).

Sequence in context: A320816 A239179 A307309 * A234267 A055420 A137746

Adjacent sequences: A186311 A186312 A186313 * A186315 A186316 A186317

Keyword

nonn,easy

Author

Toby Gottfried, Feb 17 2011

Status

approved