%I A005251 M1059
%S A005251 0,1,1,1,2,4,7,12,21,37,65,114,200,351,616,1081,1897,3329,5842,10252,
%T A005251 17991,31572,55405,97229,170625,299426,525456,922111,1618192,2839729,
%U A005251 4983377,8745217,15346786,26931732,47261895,82938844,145547525
%N A005251 a(0) = 0, a(1) = a(2) = a(3) = 1; thereafter, a(n) = a(n-1)+a(n-2)+a(n-4).
%C A005251 a(n+3) = number of n-bit sequences that avoid 010. Example: For n=4 the 
               12 sequences are all 4-bit sequences except 0100, 0101, 0010, 1010. 
               - David Callan (callan(AT)stat.wisc.edu), Mar 25 2004
%C A005251 Number of different positive braids with n crossings of 3 strands.
%C A005251 This is a_2(n) in the Doroslovacki reference. Note that there is a typo 
               in the paper in the formula for a_2(n): the upper bound in the inner 
               sum should be "n-i" not "i-1". - Max Alekseyev, Jun 26 2007
%C A005251 a(n)=number of peakless Motzkin paths of length n-1 with no UHH...HD's 
               starting at level > 0 (here n>0 and U=(1,1), H=(1,0), D=(1,-1)). 
               Example: a(5)=7 because from all 8 peakless Motzkin paths of length 
               5 (see A004148) only UUHDD does not qualify. - Emeric Deutsch (deutsch(AT)duke.poly.edu), 
               Sep 13 2004
%C A005251 Conjecture: a(n+1) + |A078065(n)| = 2*A005314(n+1) Formula generated 
               by floretion: + .5'i - .25'j + .25'k + .5i' + .25j' - .25k' - .5'jj' 
               - .5'kk' + .25'ij' - .25'ik' + .25'ji' + .5'jk' - .25'ki' + .5'kj' 
               + e ("jes", "sig" series). Note: as thousands of integer sequences 
               may be associated with any "typical" floretion, the information in 
               parenthesis plays a vital role in looking it back up. - Creighton 
               Dement (creighton.k.dement(AT)uni-oldenburg.de), Dec 21 2004
%C A005251 Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 27 2009: 
               (Start)
%C A005251 Equals the INVERT transform of (1, 0, 1, 1, 1,...); equivalent to a(n) 
               =
%C A005251 a(n-1) + a(n-3) + a(n-4) + ... (End)
%D A005251 R. Austin and R. K. Guy, Binary sequences without isolated ones, Fib. 
               Quart., 16 (1978), 84-86.
%D A005251 N. Bergeron, S. Mykytiuk, F. Sottile and S. van Willigenburg, Shifted 
               quasisymmetric functions and the Hopf algebra of peak functions, 
               math.CO/9904105, 1999.
%D A005251 A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci 
               Association, San Jose, CA, 1972, p. 112.
%D A005251 S. Burckel, Efficient methods for three strand braids (submitted).
%D A005251 John H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, 
               p. 205.
%D A005251 J. Demetrovics et al., On the number of unions in a family of sets, in 
               Combinatorial Math., Proc. 3rd Internat. Conf., Annals NY Acad. Sci., 
               555 (1989), 150-158.
%D A005251 R. L. Graham and N. J. A. Sloane, Anti-Hadamard matrices, Linear Alg. 
               Applic., 62 (1984), 113-137.
%D A005251 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%H A005251 T. D. Noe, <a href="b005251.txt">Table of n, a(n) for n=0..500</a>
%H A005251 P. Chinn and S. Heubach, <a href="http://www.cs.uwaterloo.ca/journals/
               JIS/index.html">Integer Sequences Related to Compositions without 
               2's</a>, J. Integer Seqs., Vol. 6, 2003.
%H A005251 R. Doroslovacki, <a href="http://www.emis.de/journals/MV/9434/mv943407.ps">
               Binary sequences without 011...110 (k-1 1's) for fixed k</a>, Mat. 
               Vesnik 46 (1994), no. 3-4, 93-98.
%H A005251 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=98">
               Encyclopedia of Combinatorial Structures 98</a>
%H A005251 S. Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">
               Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures</
               a>, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 
               1992.
%H A005251 S. Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">
               1031 Generating Functions and Conjectures</a>, Universit\'{e} du 
               Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
%H A005251 <a href="Sindx_Rea.html#recLCC">Index entries for sequences related to 
               linear recurrences with constant coefficients</a>
%F A005251 a(n) = 2*a(n-1)-a(n-2)+a(n-3).
%F A005251 G.f.: z(1-z)/(1-2z+z^2-z^3). - Emeric Deutsch (deutsch(AT)duke.poly.edu), 
               Sep 13 2004
%F A005251 23*a_n = 3*P_{2n+1} + 7*P_{2n} - 2*P_{2n-1}, where P_n are the Perrin 
               numbers, A001608. - D. E. Knuth, Dec 09 2008
%F A005251 a(n+1) = Sum(binomial(n-k, 2k), {k=0...n}). - Richard Ollerton (r.ollerton(AT)uws.edu.au), 
               May 12 2004
%F A005251 a(n) = sum_{j<n}[a(j)]-a(n-2) = A005314(n)-A005314(n-1) = A049853(n-1)-a(n-1) 
               = A005314(n)-a(n-2) - Henry.Bottomley (se16(AT)btinternet.com), Feb 
               21 2001
%F A005251 a(n+2) has g.f. (F_3(-x)+F_2(-x))/(F_4(-x)+F_3(-x)) = 1/(-x+1/(-x+1/(-x+1))) 
               where F_n(x) is the nth Fibonacci polynomial; see A011973. [From 
               Qiaochu Yuan (qchu(AT)mit.edu), Feb 19 2009]
%p A005251 A005251 := proc(n) option remember; if n <= 2 then n elif n = 3 then 
               4 else 2*A005251(n - 1) - A005251(n - 2) + A005251(n - 3); fi; end;
%p A005251 A005251:=(-1+z)/(-1+2*z-z**2+z**3); [S. Plouffe in his 1992 dissertation.]
%Y A005251 Cf. A004148, A049864, A118891, A005314.
%Y A005251 Bisection of Padovan sequence A000931.
%Y A005251 Sequence in context: A003293 A094974 A100671 this_sequence A014167 A103197 
               A000709
%Y A005251 Adjacent sequences: A005248 A005249 A005250 this_sequence A005252 A005253 
               A005254
%K A005251 nonn,nice,easy
%O A005251 0,5
%A A005251 N. J. A. Sloane (njas(AT)research.att.com), R. K. Guy