|
%I #27 Feb 29 2024 15:59:48
%S 14,25,45,82,150,275,505,928,1706,3137,5769,10610,19514,35891,66013,
%T 121416,223318,410745,755477,1389538,2555758,4700771,8646065,15902592,
%U 29249426,53798081,98950097,181997602,334745778,615693475,1132436853
%N Number of binary strings of length n with no substrings equal to 0001 or 1000.
%H R. H. Hardin, <a href="/A164398/b164398.txt">Table of n, a(n) for n=4..500</a>
%H W. Kuszmaul, <a href="http://arxiv.org/abs/1509.08216">Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations</a>, arXiv preprint arXiv:1509.08216 [cs.DM], 2015.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,0,-1).
%F G.f.: -x^4*(-14+3*x+5*x^2+8*x^3) / ( (x-1)*(x^3+x^2+x-1) ). - _R. J. Mathar_, Nov 28 2011
%F a(n) = a(n-1) + a(n-2) + a(n-3) - 2. - _Greg Dresden_, Feb 09 2020
%F a(n) = 2*a(n-1)-a(n-4). - _Wesley Ivan Hurt_, Apr 26 2021
%t LinearRecurrence[{2,0,0,-1}, {14, 25, 45, 82}, 50] (* _G. C. Greubel_, Sep 18 2017 *)
%o (PARI) x='x+O('x^50); Vec(-x^4*(-14+3*x+5*x^2+8*x^3)/((x-1)*(x^3+x^2+x-1) )) \\ _G. C. Greubel_, Sep 18 2017
%K nonn
%O 4,1
%A _R. H. Hardin_, Aug 14 2009
|
