|
%I M1059 #289 Jan 31 2024 08:03:25
%S 0,1,1,1,2,4,7,12,21,37,65,114,200,351,616,1081,1897,3329,5842,10252,
%T 17991,31572,55405,97229,170625,299426,525456,922111,1618192,2839729,
%U 4983377,8745217,15346786,26931732,47261895,82938844,145547525,255418101,448227521
%N a(0) = 0, a(1) = a(2) = a(3) = 1; thereafter, a(n) = a(n-1) + a(n-2) + a(n-4).
%C a(n+3) is the 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
%C 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
%C a(n+1) is the number of compositions of n avoiding the part 2. - _Joerg Arndt_, Jul 13 2014
%C Number of different positive braids with n crossings of 3 strands.
%C 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 a(n) is the 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
%C Conjecture: a(n+1) + |A078065(n)| = 2*A005314(n+1). - _Creighton Dement_, Dec 21 2004
%C 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
%C a(n) = A173022(2^(n-1) - 1)) for n > 0. - _Reinhard Zumkeller_, Feb 07 2010
%C 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
%C 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
%C For n >= 2, a(n) is the number of (n-2)-length binary words with no isolated zeros. - _Milan Janjic_, Mar 07 2015
%C 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
%C Number of DD-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are DD-equivalent iff the positions of pattern DD are identical in these paths. - _Sergey Kirgizov_, Apr 08 2018
%C From _Gus Wiseman_, Nov 25 2019: (Start)
%C For n > 0, also the number of subsets of {1, ..., n - 3} such that if x and x + 2 are both in the subset, then so is x + 1. For example, the a(3) = 1 through a(7) = 12 subsets are:
%C {} {} {} {} {}
%C {1} {1} {1} {1}
%C {2} {2} {2}
%C {1,2} {3} {3}
%C {1,2} {4}
%C {2,3} {1,2}
%C {1,2,3} {1,4}
%C {2,3}
%C {3,4}
%C {1,2,3}
%C {2,3,4}
%C {1,2,3,4}
%C (End)
%C The two-dimensional version, which counts sets of pairs where, if two pairs are separated by graph-distance 2, then the intermediate pair or pairs are also in the set, is A329871. - _Gus Wiseman_, Nov 30 2019
%C a(n+1) is the number of ways to tile a strip of length n with squares, dominoes, and tetrominoes, where the first tile cannot be a domino. - _Greg Dresden_ and _Myanna Nash_, Aug 18 2020
%D S. Burckel, Efficient methods for three strand braids (submitted). [Apparently unpublished]
%D P. Chinn and S. Heubach, "Compositions of n with no occurrence of k", Congressus Numeratium, 2002, v. 162, pp. 33-51.
%D John H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, p. 205.
%D R. K. Guy, "Anyone for Twopins?" in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A005251/b005251.txt">Table of n, a(n) for n = 0..500</a>
%H Kassie Archer, Ethan Borsh, Jensen Bridges, Christina Graves, and Millie Jeske, <a href="https://arxiv.org/abs/2312.05145">Cyclic permutations avoiding patterns in both one-line and cycle forms</a>, arXiv:2312.05145 [math.CO], 2023. See p. 2.
%H Andrei Asinowski and Cyril Banderier, <a href="https://doi.org/10.4230/LIPIcs.AofA.2020.1">On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution</a>, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) Leibniz International Proceedings in Informatics (LIPIcs) Vol. 159, 1:1-1:16.
%H R. Austin and R. K. Guy, <a href="http://www.fq.math.ca/Scanned/16-1/austin.pdf">Binary sequences without isolated ones</a>, Fib. Quart., 16 (1978), 84-86.
%H J.-L. Baril, <a href="https://doi.org/10.46298/dmtcs.2158">Avoiding patterns in irreducible permutations</a>, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016). See Table 4.
%H Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, <a href="https://arxiv.org/abs/1804.01293">Enumeration of Łukasiewicz paths modulo some patterns</a>, arXiv:1804.01293 [math.CO], 2018.
%H N. Bergeron, S. Mykytiuk, F. Sottile and S. van Willigenburg, <a href="http://arxiv.org/abs/math/9904105">Shifted quasisymmetric functions and the Hopf algebra of peak functions</a>, arXiv:math/9904105 [math.CO], 1999.
%H D. Birmajer, J. B. Gil, and M. D. Weiner, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Gil/gil6.html">On the Enumeration of Restricted Words over a Finite Alphabet</a>, J. Int. Seq. 19 (2016) # 16.1.3, Example 11.
%H A. Blecher, C. Brennan, A. Knopfmacher and H. Prodinger, <a href="http://dx.doi.org/10.1016/j.dam.2014.08.026">The height and width of bargraphs</a>, Discrete Applied Math. 180, (2015), 36-44.
%H A. Brousseau, <a href="http://www.fq.math.ca/fibonacci-tables.html">Fibonacci and Related Number Theoretic Tables</a>, Fibonacci Association, San Jose, CA, 1972, p. 112.
%H P. Chinn and S. Heubach, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL6/Heubach/heubach5.html">Integer Sequences Related to Compositions without 2's</a>, J. Integer Seqs., Vol. 6, 2003.
%H James Currie, Pascal Ochem, Narad Rampersad, and Jeffrey Shallit, <a href="https://arxiv.org/abs/2206.01776">Properties of a Ternary Infinite Word</a>, arXiv:2206.01776 [cs.DM], 2022.
%H James Currie, Pascal Ochem, Narad Rampersad, and Jeffrey Shallit, <a href="https://arxiv.org/abs/2209.09598">Complement Avoidance in Binary Words</a>, arXiv:2209.09598 [math.CO], 2022.
%H J. Demetrovics et al., <a href="http://dx.doi.org/10.1111/j.1749-6632.1989.tb22446.x">On the number of unions in a family of sets</a>, in Combinatorial Math., Proc. 3rd Internat. Conf., Annals NY Acad. Sci., 555 (1989), 150-158.
%H R. Doroslovacki, <a href="http://www.emis.de/journals/MV/9434/mv943407.pdf">Binary sequences without 011...110 (k-1 1's) for fixed k</a>, Mat. Vesnik 46 (1994), no. 3-4, 93-98.
%H Nazim Fatès, Biswanath Sethi, and Sukanta Das, <a href="https://doi.org/10.1007/978-3-319-73216-9_15">On the Reversibility of ECAs with Fully Asynchronous Updating: The Recurrence Point of View</a>, in Reversibility and Universality, Andrew Adamatzky, editor, Emergence, Complexity and Computation Vol. 30. Springer, 2018.
%H Steven Finch, <a href="https://arxiv.org/abs/2003.09458">Cantor-solus and Cantor-multus distributions</a>, arXiv:2003.09458 [math.CO], 2020.
%H R. L. Graham and N. J. A. Sloane, <a href="http://dx.doi.org/10.1016/0024-3795(84)90090-9">Anti-Hadamard matrices</a>, Linear Alg. Applic., 62 (1984), 113-137.
%H R. K. Guy, <a href="/A005251/a005251.pdf">Letter to N. J. A. Sloane, Feb 1986</a>
%H R. K. Guy, <a href="/A005251/a005251_1.pdf">Anyone for Twopins?</a>, in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15. [Annotated scanned copy, with permission]
%H V. C. Harris and C. C. Styles, <a href="http://www.fq.math.ca/Scanned/2-4/harris.pdf">A generalization of Fibonacci numbers</a>, Fib. Quart. 2 (1964) 277-289, sequence u(n,1,2).
%H V. E. Hoggatt, Jr., <a href="/A005676/a005676.pdf">7-page typed letter to N. J. A. Sloane with suggestions for new sequences</a>, circa 1977.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=98">Encyclopedia of Combinatorial Structures 98</a>
%H Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Janjic/janjic73.html">Binomial Coefficients and Enumeration of Restricted Words</a>, Journal of Integer Sequences, 2016, Vol 19, #16.7.3.
%H Vedran Krcadinac, <a href="http://www.fq.math.ca/Papers1/44-4/quartkrcadinac04_2006.pdf">A new generalization of the golden ratio</a>, Fibonacci Quart. 44 (2006), no. 4, 335-340.
%H Erkko Lehtonen and Tamás Waldhauser, <a href="https://arxiv.org/abs/2011.08522">Associative spectra of graph algebras II. Satisfaction of bracketing identities, spectrum dichotomy</a>, arXiv:2011.08522 [math.CO], 2020.
%H J. J. Madden, <a href="http://arxiv.org/abs/1707.04351">A generating function for the distribution of runs in binary words</a>, arXiv:1707.04351 [math.CO], 2017, Theorem 1.1, r=2, k=0.
%H T. Mansour and M. Shattuck, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Shattuck/shattuck3.html">Counting Peaks and Valleys in a Partition of a Set</a>, J. Int. Seq. 13 (2010), 10.6.8, Lemma 2.1, k=2, 0 peaks.
%H Denis Neiter and Amsha Proag, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Proag/proag3.html">Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers</a>, Journal of Integer Sequences, Vol. 19 (2016), Article 16.8.3.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.
%H A. G. Shannon, <a href="http://www.nntdm.net/papers/nntdm-17/NNTDM-17-4-09-13.pdf">Some recurrence relations for binary sequence matrices</a>, NNTDM 17 (2011), 4, 913.
%H Bojan Vučković and Miodrag Živković, <a href="https://www.researchgate.net/publication/312219294">Row Space Cardinalities Above 2^(n - 2) + 2^(n - 3)</a>, ResearchGate, January 2017, p. 3.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,1).
%F a(n) = 2*a(n-1) - a(n-2) + a(n-3).
%F G.f.: z*(1-z)/(1 - 2*z + z^2 - z^3). - _Emeric Deutsch_, Sep 13 2004
%F 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
%F a(n+1) = Sum_{k=0..n} binomial(n-k, 2k). - _Richard L. Ollerton_, May 12 2004
%F From _Henry Bottomley_, Feb 21 2001: (Start)
%F a(n) = (Sum_{j<n} a(j)) - a(n-2).
%F a(n) = A005314(n) - A005314(n-1).
%F a(n) = A049853(n-1) - a(n-1).
%F a(n) = A005314(n) - a(n-2). (End)
%F 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
%F BINOMIAL transform of A176971 is a(n+1). - _Michael Somos_, Dec 13 2013
%F a(n) = hypergeom([(2-n)/3, 1-n/3, (1-n)/3], [1/2, -n+1], 27/4) for n > 1. - _Peter Luschny_, Apr 08 2018
%F G.f.: z/(1-z-z^3-z^4-z^5-...) for the compositions of n-1 avoiding 2. The g.f. for the number of compositions of n avoiding the part k is 1/(1-z-...-z^(k-1) - z^(k+1)-...). - _Gregory L. Simay_, Sep 09 2018
%e From _Joerg Arndt_, Jan 26 2013: (Start)
%e The a(5+2) = 12 compositions of 5 where no two adjacent parts are != 1 are
%e [ 1] [ 1 1 1 1 1 ]
%e [ 2] [ 1 1 1 2 ]
%e [ 3] [ 1 1 2 1 ]
%e [ 4] [ 1 1 3 ]
%e [ 5] [ 1 2 1 1 ]
%e [ 6] [ 1 3 1 ]
%e [ 7] [ 1 4 ]
%e [ 8] [ 2 1 1 1 ]
%e [ 9] [ 2 1 2 ]
%e [10] [ 3 1 1 ]
%e [11] [ 4 1 ]
%e [12] [ 5 ]
%e (End)
%e 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 + ...
%p 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:=(-1+z)/(-1+2*z-z**2+z**3); # _Simon Plouffe_ in his 1992 dissertation
%p a := n -> `if`(n<=1, n, hypergeom([(2-n)/3, 1-n/3, (1-n)/3], [1/2, -n+1], 27/4)):
%p seq(simplify(a(n)), n=0..36); # _Peter Luschny_, Apr 08 2018
%t LinearRecurrence[{2,-1,1},{0,1,1},40] (* _Harvey P. Dale_, May 05 2011 *)
%t a[ n_]:= If[n<0, SeriesCoefficient[ -x(1-x)/(1 -x + 2x^2 -x^3), {x, 0, -n}], SeriesCoefficient[ x(1-x)/(1 -2x +x^2 -x^3), {x, 0, n}]] (* _Michael Somos_, Dec 13 2013 *)
%t a[0] = 1; a[1] = a[2] = 0; a[n_] := a[n] = a[n-2] + a[n-3]; Table[a[2 n-1], {n, 1, 20}] (* _Rigoberto Florez_, Oct 15 2019 *)
%t Table[If[n==0,0,Length[DeleteCases[Subsets[Range[n-3]],{___,x_,y_,___}/;x+2==y]]],{n,0,10}] (* _Gus Wiseman_, Nov 25 2019 *)
%o (Haskell)
%o a005251 n = a005251_list !! n
%o a005251_list = 0 : 1 : 1 : 1 : zipWith (+) a005251_list
%o (drop 2 $ zipWith (+) a005251_list (tail a005251_list))
%o -- _Reinhard Zumkeller_, Dec 28 2011
%o (PARI) Vec((1-x)/(1-2*x+x^2-x^3)+O(x^99)) /* _Charles R Greathouse IV_, Nov 20 2012 */
%o (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 */
%o (Magma) I:=[0,1,1,1]; [n le 4 select I[n] else Self(n-1)+Self(n-2)+Self(n-4): n in [1..45]]; // _Vincenzo Librandi_, Nov 30 2018
%o (Magma) R<x>:=PowerSeriesRing(Integers(), 40); [0] cat Coefficients(R!( x*(1-x)/(1-2*x + x^2 - x^3) )); // _Marius A. Burtea_, Oct 24 2019
%o (SageMath) [sum( binomial(n-j-1, 2*j) for j in (0..floor((n-1)/3)) ) for n in (0..50)] # _G. C. Greubel_, Apr 13 2022
%Y Cf. A001608, A004148, A005314, A006498, A011973, A049864, A049853, A078065.
%Y Cf. A118891, A173022, A176971, A178470, A261041, A303696, A329871.
%Y Bisection of Padovan sequence A000931.
%Y Partial sums of A005314 shifted 3 times to the right, if we assume A005314(0) = 1.
%Y Compositions without adjacent equal parts are A003242.
%Y Compositions without isolated parts are A114901.
%Y Row sums of A097230(n-2) for n>1.
%K nonn,nice,easy
%O 0,5
%A _N. J. A. Sloane_, _R. K. Guy_
|
