A236453 Number of length n strings on the alphabet {0,1,2} of the form 0^i 1^j 2^k such that i,j,k>=0 and if i=1 then j=k.

1, 3, 4, 8, 11, 17, 22, 30, 37, 47, 56, 68, 79, 93, 106, 122, 137, 155, 172, 192, 211, 233, 254, 278, 301, 327, 352, 380, 407, 437, 466, 498, 529, 563, 596, 632, 667, 705, 742, 782, 821, 863, 904, 948, 991, 1037, 1082, 1130, 1177, 1227, 1276, 1328, 1379, 1433, 1486, 1542

Offset

0,2

Comments

The language of all such strings is an example of a language that satisfies the conditions of the pumping lemma for regular languages but is not regular.

References

Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Co., 1997, page 89.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (2, 0, -2, 1).

Formula

G.f.: (1 + x - 2*x^2 + 2*x^3)/((1 - x)^3*(1 + x)).

For even n a(n) = A000124(n).

For odd n a(n) = A000124(n) + 1.

a(n) = (n^2 + n + 3 - (-1)^n)/2. - Giovanni Resta, Jan 26 2014

Example

a(3)=8 because we have: 000, 001, 002, 012, 111, 112, 122, 222.

Mathematica

nn=40; a=1/(1-x); CoefficientList[Series[(a-x)a^2+x/(1-x^2), {x, 0, nn}], x]
Table[(3 - (-1)^n + n + n^2)/2, {n, 0, 50}] (* Giovanni Resta, Jan 26 2014 *)
LinearRecurrence[{2, 0, -2, 1}, {1, 3, 4, 8}, 50] (* Hugo Pfoertner, Oct 10 2024 *)

Prog

(PARI) a(n) = (n^2 + n + 3 - (-1)^n)/2 \\ Charles R Greathouse IV, Apr 18 2020

Crossrefs

Cf. A000124.

Sequence in context: A133363 A186423 A156056 * A099108 A208971 A001994

Adjacent sequences: A236450 A236451 A236452 * A236454 A236455 A236456

Keyword

nonn,easy

Author

Geoffrey Critzer, Jan 26 2014

Extensions

Terms a(41) and beyond from Andrew Howroyd, Mar 27 2020

Status

approved