|
%I #34 Jun 24 2024 06:40:46
%S 1,2,4,8,12,20,32,48,76,116,176,272,412,628,960,1456,2220,3380,5136,
%T 7824,11900,18100,27552,41904,63756,97012,147568,224528,341596,519668,
%U 790656,1202864,1829996,2784180,4235728,6444176,9804092,14915636,22692448,34523824
%N Number of binary words of length n not containing the substrings 0000, 0001, 0011, 0111.
%H Ray Chandler, <a href="/A368430/b368430.txt">Table of n, a(n) for n = 0..1000</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,1,-2).
%F a(n) = a(n-1) + a(n-2) + a(n-3) - 2*a(n-4) with a(0)=1, a(1)=2, a(2)=4, and a(3)=8.
%F G.f.: (x+1)*(x^2+1)/((x-1)*(2*x^3+x^2-1)). - _Alois P. Heinz_, Dec 30 2023
%e For n=5, the a(5) = 20 words are: 00100, 00101, 01000, 01001, 01010, 01011, 01100, 01101, 10010, 10100, 10101, 10110, 11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111.
%t m={
%t {1,1,0,0,0,0,0},
%t {0,0,1,1,0,0,0},
%t {0,0,0,0,1,1,0},
%t {0,1,0,0,0,1,0},
%t {0,0,0,0,0,0,2},
%t {0,1,0,0,0,0,1},
%t {0,0,0,0,0,0,2}
%t };
%t a[0] = 1; a[n_]:=(2^n-MatrixPower[m,n][[1,7]]);
%t Table[a[n],{n,1,39}] (* _Robert P. P. McKone_, Jan 01 2024 *)
%t LinearRecurrence[{1, 1, 1, -2}, {1, 2, 4, 8}, 50] (* _Paolo Xausa_, Jun 24 2024 *)
%Y Cf. A164408, A373080.
%K nonn,easy,changed
%O 0,2
%A _Miquel A. Fiol_, Dec 24 2023
|
