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