login
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.
2
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.
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
KEYWORD
nonn,easy
AUTHOR
Geoffrey Critzer, Jan 26 2014
EXTENSIONS
Terms a(41) and beyond from Andrew Howroyd, Mar 27 2020
STATUS
approved