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

Author

Toby Gottfried, Feb 17 2011

Keywords

• nonn
• easy

Examples

			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.
		

Links

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

Crossrefs

Cf. A186244 (ternary strings which contain 00).

Programs

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 *)

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