login
Number of binary words of length n which have no 0^b 1 1 0^a 1 0 1 0^b - matches, where a=1, b=2.
2

%I #19 Sep 08 2022 08:46:06

%S 1,2,4,8,16,32,64,128,256,512,1023,2044,4084,8160,16304,32576,65088,

%T 130048,259841,519173,1037329,2072626,4141192,8274272,16532336,

%U 33032288,65999871,131870458,263482601,526449078,1051866919,2101673384,4199229896,8390234112

%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=1, b=2.

%H Alois P. Heinz, <a href="/A234591/b234591.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_10">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,0,0,0,0,0,-1,1,1).

%F G.f.: (1+x^8+x^9)/(1-2*x+x^8-x^9-x^10). - _Alois P. Heinz_, Jan 08 2014

%p a:= n-> coeff(series(-(x^9+x^8+1)/(x^10+x^9-x^8+2*x-1), x, n+1), x, n):

%p seq(a(n), n=0..40); # _Alois P. Heinz_, Jan 08 2014

%t a[n_ /; n<=9]:= 2^n; a[n_]:=a[n] =2*a[n-1] -a[n-8] +a[n-9] +a[n-10]; Table[a[n], {n, 0, 33}] (* _Jean-François Alcover_, Mar 18 2014 *)

%o (PARI) my(x='x+O('x^40)); Vec((1+x^8+x^9)/(1-2*x+x^8-x^9-x^10)) \\ _G. C. Greubel_, Sep 14 2019

%o (Magma) R<x>:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1+x^8+x^9)/(1-2*x+x^8-x^9-x^10) )); // _G. C. Greubel_, Sep 14 2019

%o (Sage)

%o def A234591_list(prec):

%o P.<x> = PowerSeriesRing(ZZ, prec)

%o return P((1+x^8+x^9)/(1-2*x+x^8-x^9-x^10)).list()

%o A234591_list(40) # _G. C. Greubel_, Sep 14 2019

%o (GAP) a:=[1,2,4,8,16,32,64,128,256,512];; for n in [11..40] do a[n]:=2*a[n-1]-a[n-8]+a[n-9]+a[n-10]; 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