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

Author

Geoffrey Critzer, Jan 26 2014

Keywords

• nonn
• easy

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.

Examples

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

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

Crossrefs

Cf. A000124.

Programs

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

PARI

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

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

Extensions

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