login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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 (list; graph; refs; listen; history; text; internal format)
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

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 3 21:09 EDT 2021. Contains 346441 sequences. (Running on oeis4.)