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

Author

Geoffrey Critzer, Jan 27 2014

Keywords

• nonn

Comments

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

Examples

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

References

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

Programs

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]

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.