|
%I #24 Feb 06 2022 06:59:29
%S 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,
%T 28,27,30,30,31,32,34,33,36,36,37,38,40,39,42,42,43,44,46,45,48,48,49,
%U 50,52,51,54,54,55,56,58,57,60,60,61
%N 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.
%C The language of all such words is an example of a context-free language that can only be generated by ambiguous grammars.
%D M. Sipser, An Introduction to the Theory of Computation, PWS Publishing Co., 1997, page 98.
%F G.f.: (1 + 2*x + 3*x^2)/(1 - x^2 - x^3 + x^5).
%F a(n) = a(n-2) + a(n-3) - a(n-5) for n >= 5.
%e a(6) = 7 because we have: 000000, 000012, 000111, 001122, 012222, 111222, 222222.
%p a:= n-> 2 +2*iquo(n, 2) -`if`(irem(n, 3)=0, 1, 0):
%p seq(a(n), n=0..100); # _Alois P. Heinz_, Jan 27 2014
%t nn=60;a=1/(1-x);b=1/(1-x^2);c=1/(1-x^3);
%t CoefficientList[Series[2 a b-c,{x,0,nn}],x]
%K nonn
%O 0,2
%A _Geoffrey Critzer_, Jan 27 2014
|
