|
| |
|
|
A005251
|
|
a(0) = 0, a(1) = a(2) = a(3) = 1; thereafter, a(n) = a(n-1)+a(n-2)+a(n-4).
(Formerly M1059)
|
|
43
| |
|
|
0, 1, 1, 1, 2, 4, 7, 12, 21, 37, 65, 114, 200, 351, 616, 1081, 1897, 3329, 5842, 10252, 17991, 31572, 55405, 97229, 170625, 299426, 525456, 922111, 1618192, 2839729, 4983377, 8745217, 15346786, 26931732, 47261895, 82938844, 145547525
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,5
|
|
|
COMMENTS
| 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
Number of different positive braids with n crossings of 3 strands.
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
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
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
Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 27 2009: (Start)
Equals the INVERT transform of (1, 0, 1, 1, 1,...); equivalent to a(n) =
a(n-1) + a(n-3) + a(n-4) + ... (End)
a(n) = A173022(2^(n-1) - 1)) for n>0. [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Feb 07 2010]
|
|
|
REFERENCES
| R. Austin and R. K. Guy, Binary sequences without isolated ones, Fib. Quart., 16 (1978), 84-86.
N. Bergeron, S. Mykytiuk, F. Sottile and S. van Willigenburg, Shifted quasisymmetric functions and the Hopf algebra of peak functions, math.CO/9904105, 1999.
A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 112.
S. Burckel, Efficient methods for three strand braids (submitted).
John H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, p. 205.
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.
R. L. Graham and N. J. A. Sloane, Anti-Hadamard matrices, Linear Alg. Applic., 62 (1984), 113-137.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=0..500
P. Chinn and S. Heubach, Integer Sequences Related to Compositions without 2's, J. Integer Seqs., Vol. 6, 2003.
R. Doroslovacki, Binary sequences without 011...110 (k-1 1's) for fixed k, Mat. Vesnik 46 (1994), no. 3-4, 93-98.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 98
S. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
Index entries for sequences related to linear recurrences with constant coefficients
|
|
|
FORMULA
| a(n) = 2*a(n-1)-a(n-2)+a(n-3).
G.f.: z(1-z)/(1-2z+z^2-z^3). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Sep 13 2004
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
a(n+1) = Sum(binomial(n-k, 2k), {k=0...n}). - Richard Ollerton (r.ollerton(AT)uws.edu.au), May 12 2004
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
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 n-th Fibonacci polynomial; see A011973. [From Qiaochu Yuan (qchu(AT)mit.edu), Feb 19 2009]
|
|
|
MAPLE
| 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;
A005251:=(-1+z)/(-1+2*z-z**2+z**3); [S. Plouffe in his 1992 dissertation.]
|
|
|
MATHEMATICA
| LinearRecurrence[{2, -1, 1}, {0, 1, 1}, 40] (* From Harvey P. Dale, May 05 2011 *)
|
|
|
PROG
| (Haskell)
a005251 n = a005251_list !! (n-1)
a005251_list = 0 : 1 : 1 : 1 : zipWith (+) a005251_list
(drop 2 $ zipWith (+) a005251_list (tail a005251_list))
-- Reinhard Zumkeller, Dec 28 2011
|
|
|
CROSSREFS
| Cf. A004148, A049864, A118891, A005314.
Bisection of Padovan sequence A000931.
Sequence in context: A189593 A100671 A189600 * A014167 A103197 A000709
Adjacent sequences: A005248 A005249 A005250 * A005252 A005253 A005254
|
|
|
KEYWORD
| nonn,nice,easy
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), R. K. Guy
|
| |
|
|
