login
Number of binary strings of length n avoiding substrings 1000, 1011, 1101, or 1111.
1

%I #13 Nov 02 2021 04:34:26

%S 1,2,4,8,12,18,27,41,61,88,129,189,276,401,582,848,1233,1791,2601,

%T 3779,5492,7976,11584,16826,24441,35500,51558,74885,108767,157976,

%U 229445,333247,484017,702994,1021035,1482962,2153874,3128318,4543603,6599180,9584730

%N Number of binary strings of length n avoiding substrings 1000, 1011, 1101, or 1111.

%H Alois P. Heinz, <a href="/A294049/b294049.txt">Table of n, a(n) for n = 0..2000</a>

%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,0,0,0,-2,0,1)

%F G.f.: (x+1)*(x^5+x^4-x^3-x^2-1)/((x-1)*(x^7+x^6-x^5-x^4-x^3-x^2+1)).

%p a:= n-> (Matrix(8, (i, j)-> `if`(i+1=j, 1, `if`(i=8,

%p [1, 0, -2, 0$3, 1$2][j], 0)))^n. <<1, 2, 4, 8, 12, 18, 27, 41>>)[1$2]:

%p seq(a(n), n=0..45);

%t LinearRecurrence[{1, 1, 0, 0, 0, -2, 0, 1}, {1, 2, 4, 8, 12, 18, 27, 41}, 40] (* _Jean-François Alcover_, Nov 02 2021 *)

%Y Cf. A164417, A164420.

%K nonn,easy

%O 0,2

%A _Alois P. Heinz_, Oct 22 2017