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