A335551 Number of words of length n over the alphabet {0,1,2} that contain the substring 12 but not the substring 01.

0, 0, 1, 5, 18, 58, 177, 522, 1503, 4252, 11869, 32787, 89821, 244415, 661415, 1781654, 4780776, 12786704, 34104792, 90749209, 240982564, 638800052, 1690764378, 4469170031, 11799684559, 31122693066, 82016622160, 215969175981, 568313267862, 1494601936229

Offset

0,4

Links

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

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

Formula

a(n) = Sum_{i=1..n} A001906(n-i) * A052921(i-1).

G.f.: x^2*(x-1)/((x^2-3*x+1)*(x^3-2*x^2+3*x-1)). - Alois P. Heinz, Sep 15 2020

Example

a(0) = a(1) = 0, because no word of length n < 2 can contain 12.
a(2) = 1, because there is one word of length 2 and it is 12.
a(3) = 5, because there are 5 words of length 3 and they are 121, 112, 212, 122, 120.

Crossrefs

Cf. A001906, A052921.

Sequence in context: A128553 A190163 A364553 * A235612 A000340 A301880

Adjacent sequences: A335548 A335549 A335550 * A335552 A335553 A335554

Keyword

nonn,easy

Author

Mauricio J. Santos, Sep 15 2020

Extensions

a(20)-a(29) from Alois P. Heinz, Sep 15 2020

Status

approved