|
%I #17 Sep 08 2022 08:46:06
%S 1,2,4,8,16,32,64,128,256,511,1020,2036,4064,8112,16192,32320,64513,
%T 128773,257041,513074,1024136,2044256,4080496,8144991,16258042,
%U 32452329,64777398,129300775,258094504,515176904,1028333569,2052634583,4097219870,8178372713
%N Number of binary words of length n which have no 0^b 1 1 0^a 1 0 1 0^b - matches, where a=0, b=2.
%H Alois P. Heinz, <a href="/A234590/b234590.txt">Table of n, a(n) for n = 0..1000</a>
%H B. K. Miceli, J, Remmel, <a href="http://puma.dimai.unifi.it/23_3/miceli_remmel.pdf">Minimal Overlapping Embeddings and Exact Matches in Words</a>, PU. M. A., Vol. 23 (2012), No. 3, pp. 291-315.
%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,0,0,0,0,-1,1,1).
%F G.f.: (1+x^7+x^8)/(1-2*x+x^7-x^8-x^9). - _Alois P. Heinz_, Jan 08 2014
%p a:= n-> coeff(series(-(x^8+x^7+1)/(x^9+x^8-x^7+2*x-1), x, n+1), x, n):
%p seq(a(n), n=0..60); # _Alois P. Heinz_, Jan 08 2014
%t a[n_ /; n<=8]:= 2^n; a[n_]:= a[n] =2*a[n-1] -a[n-7] +a[n-8] +a[n-9]; Table[a[n], {n, 0, 33}] (* _Jean-François Alcover_, Mar 18 2014 *)
%o (PARI) my(x='x+O('x^60)); Vec((1+x^7+x^8)/(1-2*x+x^7-x^8-x^9)) \\ _G. C. Greubel_, Sep 14 2019
%o (Magma) I:=[1,2,4,8,16,32,64,128,256]; [n le 9 select I[n] else 2*Self(n-1) - Self(n-7) + Self(n-8) + Self(n-9): n in [1..60]]; // _G. C. Greubel_, Sep 14 2019
%o (Sage)
%o def A234590_list(prec):
%o P.<x> = PowerSeriesRing(ZZ, prec)
%o return P((1+x^7+x^8)/(1-2*x+x^7-x^8-x^9)).list()
%o A234590_list(60) # _G. C. Greubel_, Sep 14 2019
%o (GAP) a:=[1,2,4,8,16,32,64,128,256];; for n in [10..60] do a[n]:=2*a[n-1] -a[n-7]+a[n-8]+a[n-9]; od; a; # _G. C. Greubel_, Sep 14 2019
%K nonn,easy
%O 0,2
%A _N. J. A. Sloane_, Jan 01 2014
%E a(17)-a(33) from _Alois P. Heinz_, Jan 08 2014
|
