login
This site is supported by donations to The OEIS Foundation.

 

Logo

"Email this user" was broken Aug 14 to 9am Aug 16. If you sent someone a message in this period, please send it again.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)
116
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; text; 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, Mar 25 2004

a(n+2) is the number of compositions (ordered partitions) of n where no two adjacent parts are != 1, see example. - Joerg Arndt, Jan 26 2013

a(n+1) is the number of compositions of n avoiding the part 2. - Joerg Arndt, Jul 13 2014

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, Sep 13 2004

Conjecture: a(n+1) + |A078065(n)| = 2*A005314(n+1). - Creighton Dement, Dec 21 2004

Equals the INVERT transform of (1, 0, 1, 1, 1,...); equivalent to a(n) = a(n-1) + a(n-3) + a(n-4) + ... - Gary W. Adamson, Apr 27 2009

a(n) = A173022(2^(n-1) - 1)) for n>0. - Reinhard Zumkeller, Feb 07 2010

a(n) is the number of length n-1 words on {0,1} such that each string of 1's is followed by a string of at least two 0's. For example, a(5) = 4 because we have: 0000, 0100, 1000, and 1100. - Geoffrey Critzer, Aug 09 2013

a(n+1) is the top left entry of the n-th power of any of the 3 X 3 matrices [1, 1, 0; 0, 1, 1; 1, 0, 0] or [1, 0, 1; 1, 1, 0; 0, 1, 0] or [1, 1, 0; 0, 0, 1; 1, 0, 1] or [1, 0, 1; 1, 0, 0; 0, 1, 1]. - R. J. Mathar, Feb 03 2014

For n>=2, a(n) is the number of (n-2)-length binary words with no isolated zeros. - Milan Janjic, Mar 07 2015

Apart from the first three terms, the total number of bargraphs of semiperimeter n of height at most two for n>=2 starts 1, 2, 4, 7, 12, ... - Arnold Knopfmacher, Nov 02 2016

REFERENCES

S. Burckel, Efficient methods for three strand braids (submitted). [Apparently unpublished]

John H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, p. 205.

R. K. Guy, "Anyone for Twopins?" in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15.

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

R. Austin and R. K. Guy, Binary sequences without isolated ones, Fib. Quart., 16 (1978), 84-86.

J.-L. Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science,  Vol 17, No 3 (2016). See Table 4.

N. Bergeron, S. Mykytiuk, F. Sottile and S. van Willigenburg, Shifted quasisymmetric functions and the Hopf algebra of peak functions, arXiv:math/9904105 [math.CO], 1999.

A. Blecher, C. Brennan, A. Knopfmacher and H. Prodinger, The height and width of bargraphs, Discrete Applied Math. 180, (2015), 36-44.

A. Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972, p. 112.

P. Chinn and S. Heubach, Integer Sequences Related to Compositions without 2's, J. Integer Seqs., Vol. 6, 2003.

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. Doroslovacki, Binary sequences without 011...110 (k-1 1's) for fixed k, Mat. Vesnik 46 (1994), no. 3-4, 93-98.

R. L. Graham and N. J. A. Sloane, Anti-Hadamard matrices, Linear Alg. Applic., 62 (1984), 113-137.

R. K. Guy, Letter to N. J. A. Sloane, Feb 1986

V. C. Harris, C. C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277-289, sequence u(n,1,2).

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 98

Vedran Krcadinac, A new generalization of the golden ratio, Fibonacci Quart. 44 (2006), no. 4, 335-340.

J. J. Madden, A generating function for the distribution of runs in binary words, arXiv:1707.04351 [math.CO], 2017, Theorem 1.1, r=2, k=0.

T. Mansour, M. Shattuck, Counting Peaks and Valleys in a Partition of a Set , J. Int. Seq. 13 (2010), 10.6.8, Lemma 2.1, k=2, 0 peaks.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

A. G. Shannon, Some recurrence relations for binary sequence matrices, NNTDM 17 (2011), 4, 913.

Index entries for linear recurrences with constant coefficients, signature (2,-1,1)

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, 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. - Don 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, 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. - Qiaochu Yuan (qchu(AT)mit.edu), Feb 19 2009

BINOMIAL transform of A176971 is a(n+1). - Michael Somos, Dec 13 2013

EXAMPLE

From Joerg Arndt, Jan 26 2013: (Start)

The a(5+2) = 12 compositions of 5 where no two adjacent parts are != 1 are

[ 1]  [ 1 1 1 1 1 ]

[ 2]  [ 1 1 1 2 ]

[ 3]  [ 1 1 2 1 ]

[ 4]  [ 1 1 3 ]

[ 5]  [ 1 2 1 1 ]

[ 6]  [ 1 3 1 ]

[ 7]  [ 1 4 ]

[ 8]  [ 2 1 1 1 ]

[ 9]  [ 2 1 2 ]

[10]  [ 3 1 1 ]

[11]  [ 4 1 ]

[12]  [ 5 ]

(End)

G.f. = x + x^2 + x^3 + 2*x^4 + 4*x^5 + 7*x^6 + 12*x^7 + 21*x^8 + 37*x^9 + ...

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); # Simon Plouffe in his 1992 dissertation

MATHEMATICA

LinearRecurrence[{2, -1, 1}, {0, 1, 1}, 40]  (* Harvey P. Dale, May 05 2011 *)

a[ n_] := If[ n < 0, SeriesCoefficient[ -x (1 - x) / (1 - x + 2 x^2 - x^3), {x, 0, -n}], SeriesCoefficient[ x (1 - x) / (1 - 2 x + x^2 - x^3), {x, 0, n}]] (* Michael Somos, Dec 13 2013 *)

PROG

(Haskell)

a005251 n = a005251_list !! n

a005251_list = 0 : 1 : 1 : 1 : zipWith (+) a005251_list

   (drop 2 $ zipWith (+) a005251_list (tail a005251_list))

-- Reinhard Zumkeller, Dec 28 2011

(PARI) Vec((1-x)/(1-2*x+x^2-x^3)+O(x^99)) /* Charles R Greathouse IV, Nov 20 2012 */

(PARI) {a(n) = if( n<0, polcoeff( -x * (1 - x) / (1 - x + 2*x^2 - x^3) + x * O(x^-n), -n), polcoeff( x * (1 - x) / (1 - 2*x + x^2 - x^3) + x * O(x^n), n))} /* Michael Somos, Dec 13 2013 */

CROSSREFS

Cf. A004148, A005314, A049864, A118891, A176971.

Bisection of Padovan sequence A000931.

Sequence in context: A189593 A100671 A189600 * A014167 A103197 A255062

Adjacent sequences:  A005248 A005249 A005250 * A005252 A005253 A005254

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane, R. K. Guy

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 19 14:06 EDT 2017. Contains 290808 sequences.