A235451 Number of length n words on alphabet {0,1,2} of the form 0^(i)1^(j)2^(k) such that i=j or j=k.

1, 2, 4, 3, 6, 6, 7, 8, 10, 9, 12, 12, 13, 14, 16, 15, 18, 18, 19, 20, 22, 21, 24, 24, 25, 26, 28, 27, 30, 30, 31, 32, 34, 33, 36, 36, 37, 38, 40, 39, 42, 42, 43, 44, 46, 45, 48, 48, 49, 50, 52, 51, 54, 54, 55, 56, 58, 57, 60, 60, 61

Offset

0,2

Comments

The language of all such words is an example of a context-free language that can only be generated by ambiguous grammars.

References

M. Sipser, An Introduction to the Theory of Computation, PWS Publishing Co., 1997, page 98.

Links

Table of n, a(n) for n=0..60.

Formula

G.f.: (1 + 2*x + 3*x^2)/(1 - x^2 - x^3 + x^5).

a(n) = a(n-2) + a(n-3) - a(n-5) for n >= 5.

Example

a(6) = 7 because we have: 000000, 000012, 000111, 001122, 012222, 111222, 222222.

Maple

a:= n-> 2 +2*iquo(n, 2) -`if`(irem(n, 3)=0, 1, 0):
seq(a(n), n=0..100);  # Alois P. Heinz, Jan 27 2014

Mathematica

nn=60; a=1/(1-x); b=1/(1-x^2); c=1/(1-x^3);
CoefficientList[Series[2 a b-c, {x, 0, nn}], x]

Crossrefs

Sequence in context: A141429 A309131 A162953 * A348915 A039819 A242424

Adjacent sequences: A235448 A235449 A235450 * A235452 A235453 A235454

Keyword

nonn

Author

Geoffrey Critzer, Jan 27 2014

Status

approved