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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000930 Narayana's cows sequence: a(0) = a(1) = a(2) = 1; thereafter a(n) = a(n-1) + a(n-3).
(Formerly M0571 N0207)
236

%I M0571 N0207

%S 1,1,1,2,3,4,6,9,13,19,28,41,60,88,129,189,277,406,595,872,1278,1873,

%T 2745,4023,5896,8641,12664,18560,27201,39865,58425,85626,125491,

%U 183916,269542,395033,578949,848491,1243524,1822473,2670964,3914488,5736961,8407925

%N Narayana's cows sequence: a(0) = a(1) = a(2) = 1; thereafter a(n) = a(n-1) + a(n-3).

%C Named after a 14th-century Indian mathematician.

%C Number of compositions of n into parts 1 and 3. - _Joerg Arndt_, Jun 25 2011

%C A Lamé sequence of higher order.

%C Could have begun 1,0,0,1,1,1,2,3,4,6,9,... (A078012) but that would spoil many nice properties.

%C Number of tilings of a 3 X n rectangle with straight trominoes.

%C Number of ways to arrange n-1 tatami mats in a 2 X (n-1) room such that no 4 meet at a point. For example, there are 6 ways to cover a 2 X 5 room, described by 11111, 2111, 1211, 1121, 1112, 212.

%C Equivalently, number of compositions (ordered partitions) of n-1 into parts 1 and 2 with no two 2's adjacent. E.g., there are 6 such ways to partition 5, namely 11111, 2111, 1211, 1121, 1112, 212, so a(9) = 6.

%C This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n-1) + a(n-m), with a(n) = 1 for n = 0...m-1. The generating function is 1/(1-x-x^m). Also a(n) = Sum_{i=0..floor(n/m)} binomial(n-(m-1)*i, i). This family of binomial summations or recurrences gives the number of ways to cover (without overlapping) a linear lattice of n sites with molecules that are m sites wide. Special case: m=1: A000079; m=4: A003269; m=5: A003520; m=6: A005708; m=7: A005709; m=8: A005710.

%C a(n+2) = number of n-bit 0-1 sequences that avoid both 00 and 010. - _David Callan_, Mar 25 2004 [This can easily be proved by the Cluster Method - see for example the Noonan-Zeilberger article. - _N. J. A. Sloane_, Aug 29 2013]

%C a(n-4) = number of n-bit sequences that start and end with 0 but avoid both 00 and 010. For n >= 6, such a sequence necessarily starts 011 and ends 110; deleting these 6 bits is a bijection to the preceding item. - _David Callan_, Mar 25 2004

%C Also number of compositions of n+1 into parts congruent to 1 mod m. Here m=3, A003269 for m=4, etc. - _Vladeta Jovovic_, Feb 09 2005

%C Row sums of Riordan array (1/(1-x^3), x/(1-x^3)). - _Paul Barry_, Feb 25 2005

%C Row sums of Riordan array (1,x(1+x^2)). - _Paul Barry_, Jan 12 2006

%C Starting with offset 1 = row sums of triangle A145580. - _Gary W. Adamson_, Oct 13 2008

%C Number of digits in A061582. - _Dmitry Kamenetsky_, Jan 17 2009

%C The family a(n) = a(n-1) + a(n-m) with a(n)=1 for n=0..m-1 can be generated by considering the sums:

%C 1 1 1 1 1 1 1 1 1 1 1 1 1

%C 1 2 3 4 5 6 7 8 9 10

%C 1 3 6 10 15 21 28

%C 1 4 10 20

%C 1

%C ------------------------------

%C 1 1 1 2 3 4 6 9 13 19 28 41 60

%C with (in this case 3) leading zeros added to each row.

%C Number of pairs of rabbits existing at period n generated by 1 pair. All pairs become fertile after 3 periods and generate thereafter a new pair at all following periods. - _Carmine Suriano_, Mar 20 2011

%C The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=3, 2*a(n-3) equals the number of 2-colored compositions of n with all parts >= 3, such that no adjacent parts have the same color. - _Milan Janjic_, Nov 27 2011

%C For n>=2, row sums of Pascal's triangle (A007318) with triplicated diagonals. - _Vladimir Shevelev_, Apr 12 2012

%C Pisano period lengths of the sequence read mod m, m >= 1: 1, 7, 8, 14, 31, 56, 57, 28, 24, 217, 60, 56, 168, ... (A271953) If m=3, for example, the remainder sequence becomes 1, 1, 1, 2, 0, 1, 0, 0, 1, 1, 1, 2, 0, 1, 0, 0, 1, 1, 1, 2, 0, 1, 0, 0, 1, 1, 1, 2, 0, 1, 0, 0, 1, 1, ... with a period of length 8. - _R. J. Mathar_, Oct 18 2012

%C Diagonal sums of triangle A011973. - _John Molokach_, Jul 06 2013

%C "In how many ways can a kangaroo jump through all points of the integer interval [1,n+1] starting at 1 and ending at n+1, while making hops that are restricted to {-1,1,2}? (The OGF is the rational function 1/(1 - z - z^3) corresponding to A000930.)" [Flajolet and Sedgewick, p. 373] - _N. J. A. Sloane_, Aug 29 2013

%C a(n) is the number of length n binary words in which the length of every maximal run of consecutive 0's is a multiple of 3. a(5) = 4 because we have: 00011, 10001, 11000, 11111. - _Geoffrey Critzer_, Jan 07 2014

%C a(n) is the top left entry of the n-th power of the 3X3 matrix [1, 0, 1; 1, 0, 0; 0, 1, 0] or of the 3 X 3 matrix [1, 1, 0; 0, 0, 1; 1, 0, 0]. - _R. J. Mathar_, Feb 03 2014

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

%C Counts closed walks of length (n+3) on a unidirectional triangle, containing a loop at one of remaining vertices. - _David Neil McGrath_, Sep 15 2014

%C a(n+2) equals the number of binary words of length n, having at least two zeros between every two successive ones. - _Milan Janjic_, Feb 07 2015

%C a(n+1)/a(n) tends to x = 1.465571... (decimal expansion given in A092526) in the limit n -> infinity. This is the real solution of x^3 - x^2 -1 = 0. See also the formula by _Benoit Cloitre_, Nov 30 2002. - _Wolfdieter Lang_, Apr 24 2015

%C a(n+2) equals the number of subsets of {1,2,..,n} in which any two elements differ by at least 3. - _Robert FERREOL_, Feb 17 2016

%C Let T* be the infinite tree with root 0 generated by these rules: if p is in T*, then p+1 is in T* and x*p is in T*. Let g(n) be the set of nodes in the n-th generation, so that g(0) = {0}, g(1) = {1}, g(2) = {2,x}, g(3) = {3,2x,x+1,x^2}, etc. Let T(r) be the tree obtained by substituting r for x. If a positive integer N such that r = N^(1/3) is not an integer, then the number of (not necessarily distinct) integers in g(n) is A000930(n), for n >= 1. (See A274142.) - _Clark Kimberling_, Jun 13 2016

%C a(n-3) is the number of compositions of n excluding 1 and 2, n >= 3. - _Gregory L. Simay_, Jul 12 2016

%D A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A., 2003, id. 8,80.

%D R. K. Guy, "Anyone for Twopins?" in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15. [See p. 12, line 3]

%D H. Langman, Play Mathematics. Hafner, NY, 1962, p. 13.

%D David Sankoff and Lani Haque, Power Boosts for Cluster Tests, in Comparative Genomics, Lecture Notes in Computer Science, Volume 3678/2005, Springer-Verlag. - _N. J. A. Sloane_, Jul 09 2009

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Harvey P. Dale and T. D. Noe, <a href="/A000930/b000930.txt">Table of n, a(n) for n = 0..5000</a> [The first 500 terms were computed by T. D. Noe]

%H Gene Abrams, Stefan Erickson, Cristóbal Gil Canto, <a href="https://arxiv.org/abs/1712.06480">Leavitt path algebras of Cayley graphs C_n^j</a>, arXiv:1712.06480 [math.RA], 2017.

%H J.-P. Allouche and T. Johnson, <a href="http://jim.afim-asso.org/jim96/actes/Allouche.ps">Narayana's Cows and Delayed Morphisms</a>, 3rd Computer Music Conference, 1996.

%H J.-P. Allouche and T. Johnson, <a href="http://kalvos.org/johness1.html">Narayana's Cows and Delayed Morphisms</a>

%H I. Amburg, K. Dasaratha, L. Flapan, T. Garrity, C. Lee, C. Mihailak, N. Neumann-Chun, S. Peluse, M. Stoffregen, <a href="http://arxiv.org/abs/1509.05239">Stern Sequences for a Family of Multidimensional Continued Fractions: TRIP-Stern Sequences</a>, arXiv:1509.05239v1 [math.CO] Sep 17 2015. See Conjecture 5.8.

%H Bruce M. Boman, Thien-Nam Dinh, Keith Decker, Brooks Emerick, Christopher Raymond, Gilberto Schleinger, <a href="https://www.fq.math.ca/Papers1/55-5/Boman.pdf">Why do Fibonacci numbers appear in patterns of growth in nature?</a>, in Fibonacci Quarterly, 55(5): pp 30-41, (2017).

%H Russ Chamberlain, Sam Ginsburg and Chi Zhang, <a href="http://digital.library.wisc.edu/1793/61870">Generating Functions and Wilf-equivalence on Theta_k-embeddings</a>, University of Wisconsin, April 2012.

%H Eunice Y. S. Chan, <a href="http://ir.lib.uwo.ca/etd/4028">A comparison of solution methods for Mandelbrot-like polynomials</a>, MS Thesis, 2016, University of Western Ontario; Electronic Thesis and Dissertation Repository. 4028.

%H Eunice Y. S. Chan, Robert Corless, <a href="https://doi.org/10.13001/1081-3810.3400">A new kind of companion matrix</a>, Electronic Journal of Linear Algebra, Volume 32, Article 25, 2017, see p. 339.

%H E. Di Cera and Y. Kong, <a href="http://dx.doi.org/10.1016/S0301-4622(96)02178-3">Theory of multivalent binding in one and two-dimensional lattices</a>, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.

%H James East, Nicholas Ham, <a href="https://arxiv.org/abs/1811.05735">Lattice paths and submonoids of Z^2</a>, arXiv:1811.05735 [math.CO], 2018.

%H Larry Ericksen and Peter G. Anderson, <a href="http://www.cs.rit.edu/~pga/k-zeck.pdf">Patterns in differences between rows in k-Zeckendorf arrays</a>, The Fibonacci Quarterly, Vol. 50, February 2012. - _N. J. A. Sloane_, Jun 10 2012

%H M. Feinberg, <a href="http://www.fq.math.ca/Scanned/2-3/feinberg.pdf">New slants</a>, Fib. Quart. 2 (1964), 223-227.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 373

%H I. M. Gessel, Ji Li, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Gessel/gessel6.html">Compositions and Fibonacci identities</a>, J. Int. Seq. 16 (2013) 13.4.5

%H Philip Gibbs, Judson McCranie, <a href="https://www.researchgate.net/profile/Philip_Gibbs/publication/320980165_The_Ulam_Numbers_up_to_One_Trillion/links/5a058786aca2726b4c78588d/The-Ulam-Numbers-up-to-One-Trillion.pdf">The Ulam Numbers up to One Trillion</a>, (2017).

%H Maria M. Gillespie, Kenneth G. Monks, Kenneth M. Monks, <a href="https://arxiv.org/abs/1808.03573">Enumerating Anchored Permutations with Bounded Gaps</a>, arXiv:1808.03573 [math.CO], 2018.

%H Taras Goy, <a href="https://doi.org/10.33039/ami.2018.09.001">On identities with multinomial coefficients for Fibonacci-Narayana sequence</a>, Annales Mathematicae et Informaticae (2018) 49, Eszterházy Károly University Institute of Mathematics and Informatics, 75-84.

%H T. M. Green, <a href="http://www.jstor.org/stable/2687953">Recurrent sequences and Pascal's triangle</a>, Math. Mag., 41 (1968), 13-21.

%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 R. K. Guy, <a href="/A005165/a005165.pdf">The strong law of small numbers</a>, Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]

%H V. C. Harris, 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,2,1).

%H W. R. Heinson, <a href="http://hdl.handle.net/2097/19714">Simulation studies on shape and growth kinetics for fractal aggregates in aerosol and colloidal systems</a>, PhD Dissertation, Kansas State Univ., Manhattan, Kansas, 2015; see page 49.

%H J. Hermes, <a href="http://dx.doi.org/10.1007/BF01446684">Anzahl der Zerlegungen einer ganzen rationalen Zahl in Summanden</a>, Math. Ann., 45 (1894), 371-380.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=14">Encyclopedia of Combinatorial Structures 14</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=376">Encyclopedia of Combinatorial Structures 376</a>

%H M. Janjic, <a href="http://arxiv.org/abs/1112.2466">Recurrence Relations and Determinants</a>, arXiv preprint arXiv:1112.2466 [math.CO], 2011.

%H M. Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Janjic/janjic42.html">Determinants and Recurrence Sequences</a>, Journal of Integer Sequences, 2012, Article 12.3.5.

%H Dov Jarden, <a href="/A001602/a001602.pdf">Recurring Sequences</a>, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 91.

%H Tom Johnson, <a href="https://www.youtube.com/watch?v=VOS3piSMS9E">Illustrated Music #8, Narayana’s Cows</a>

%H B. Keszegh, N Lemons and D. Palvolgyi, <a href="http://arxiv.org/abs/1207.4415">Online and quasi-online colorings of wedges and intervals</a>, arXiv preprint arXiv:1207.4415 [math.CO], 2012-2015.

%H K. Kirthi, <a href="http://arxiv.org/abs/1509.05745">Narayana Sequences for Cryptographic Applications</a>, arXiv preprint arXiv:1509.05745 [math.NT], 2015.

%H Steven Linton, James Propp, Tom Roby, Julian West, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Roby/roby4.html">Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions</a>, Journal of Integer Sequences, Vol. 15 (2012), #12.9.1.

%H K. Manes, A. Sapounakis, I. Tasoulas, P. Tsikouras, <a href="http://arxiv.org/abs/1510.01952">Equivalence classes of ballot paths modulo strings of length 2 and 3</a>, arXiv:1510.01952 [math.CO], 2015.

%H T. Mansour and M. Shattuck, <a href="http://dx.doi.org/10.1016/j.amc.2012.12.052">Polynomials whose coefficients are generalized Tribonacci numbers</a>, Applied Mathematics and Computation, Volume 219, Issue 15, Apr 01 2013, Pages 8366-8374.

%H T. Mansour, M. Shattuck, <a href="http://arxiv.org/abs/1410.6943">A monotonicity property for generalized Fibonacci sequences</a>, arXiv preprint arXiv:1410.6943 [math.CO], 2014.

%H R. J. Mathar, <a href="http://arxiv.org/abs/1311.6135">Paving Rectangular Regions with Rectangular Tiles: Tatami and Non-Tatami Tilings</a>, arXiv:1311.6135 [math.CO], 2013, Table 17.

%H R. J. Mathar, <a href="http://arxiv.org/abs/1609.03964">Tiling n x m rectangles with 1 x 1 and s x s squares</a>, arXiv:1609.03964 (2016), Section 4.2.

%H Augustine O. Munagi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Munagi/munagi10.html">Integer Compositions and Higher-Order Conjugation</a>, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.

%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), #16.8.3.

%H J. Noonan and D. Zeilberger, <a href="http://arxiv.org/abs/math/9806036">The Goulden-Jackson Cluster Method: Extensions, Applications and Implementations</a>, arXiv:math/9806036 [math.CO], Jun 08 1998.

%H Antonio M. Oller-Marcén, <a href="http://www.emis.de/journals/INTEGERS/papers/j11/j11.Abstract.html">The Dying Rabbit Problem Revisited</a>, INTEGERS, 9 (2009), 129-138

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992.

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">1031 Generating Functions and Conjectures</a>, Université du Québec à Montréal, 1992.

%H M. Randic, D. Morales, O. Araujo, <a href="http://www.emis.de/journals/DM/v16-2/art3.pdf">Higher-order Lucas numbers</a>, Divulgaciones Matematicas 6:2 (2008), pp. 275-283.

%H F. Ruskey and J. Woodcock, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v16i1r126">Counting Fixed-Height Tatami Tilings</a>, Electronic Journal of Combinatorics, Paper R126 (2009), 20 pages.

%H T. Sillke, <a href="http://www.mathematik.uni-bielefeld.de/~sillke/SEQUENCES/series001">The binary form of Conway's Sequence</a>

%H Z. Skupien, <a href="http://dx.doi.org/10.1016/j.disc.2008.11.003">Sparse Hamiltonian 2-decompositions together with exact count of numerous Hamiltonian cycles</a>, Discr. Math., 309 (2009), 6382-6390. - _N. J. A. Sloane_, Feb 12 2010

%H Krzysztof Strasburger, <a href="http://dx.doi.org/10.1063/1.4953677">The order of three lowest-energy states of the six-electron harmonium at small force constant</a>, The Journal of Chemical Physics 144, 234304 (2016).

%H E. Wilson, <a href="http://www.anaphoria.com/meruone.PDF">The Scales of Mt. Meru</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,1).

%F G.f.: 1/(1-x-x^3). - _Simon Plouffe_ in his 1992 dissertation

%F a(n) = Sum_{i=0..floor(n/3)} binomial(n-2*i, i).

%F a(n) = a(n-2) + a(n-3) + a(n-4) for n>3.

%F a(n) = floor(d*c^n + 1/2) where c is the real root of x^3-x^2-1 and d is the real root of 31*x^3-31*x^2+9*x-1 (c = 1.465571... = A092526 and d = 0.611491991950812...). - _Benoit Cloitre_, Nov 30 2002

%F a(n) = Sum_{k=0..n} binomial(floor((n+2k-2)/3), k). - _Paul Barry_, Jul 06 2004

%F a(n) = Sum_{k=0..n} binomial(k, floor((n-k)/2))(1+(-1)^(n-k))/2. - _Paul Barry_, Jan 12 2006

%F a(n) = Sum_{k=0..n} binomial((n+2k)/3,(n-k)/3)*(2*cos(2*Pi*(n-k)/3)+1)/3. - _Paul Barry_, Dec 15 2006

%F a(n) = term (1,1) in matrix [1,1,0; 0,0,1; 1,0,0]^n. - _Alois P. Heinz_, Jun 20 2008

%F G.f.: exp( Sum_{n>=1} ((1+sqrt(1+4*x))^n + (1-sqrt(1+4*x))^n)*(x/2)^n/n ).

%F Logarithmic derivative equals A001609. - _Paul D. Hanna_, Oct 08 2009

%F a(n) = a(n-1) + a(n-2) - a(n-5) for n>4. - _Paul Weisenhorn_, Oct 28 2011

%F For n >= 2, a(2*n-1) = a(2*n-2)+a(2*n-4); a(2*n) = a(2*n-1)+a(2*n-3). - _Vladimir Shevelev_, Apr 12 2012

%F INVERT transform of (1,0,0,1,0,0,1,0,0,1,...) = (1, 1, 1, 2, 3, 4, 6, ...); but INVERT transform of (1,0,1,0,0,0,...) = (1, 1, 2, 3, 4, 6, ...). - _Gary W. Adamson_, Jul 05 2012

%F G.f.: 1/(G(0)-x) where G(k) = 1 - x^2/(1 - x^2/(x^2 - 1/G(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Dec 16 2012

%F G.f.: 1 + x/(G(0)-x) where G(k) = 1 - x^2*(2*k^2 + 3*k +2) + x^2*(k+1)^2*(1 - x^2*(k^2 + 3*k +2))/G(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Dec 27 2012

%F a(2*n) = A002478(n), a(2*n+1) = A141015(n+1), a(3*n) = A052544(n), a(3*n+1) = A124820(n), a(3*n+2) = A052529(n). - _Johannes W. Meijer_, Jul 21 2013

%F G.f.: Q(0)/2, where Q(k) = 1 + 1/(1 - x*(4*k+1 + x^2)/( x*(4*k+3 + x^2) + 1/Q(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Sep 08 2013

%F a(n) = v1*w1^n+v3*w2^n+v2*w3^n, where v1,2,3 are the roots of (-1+9*x-31*x^2+31*x^3): [v1=0.6114919920, v2=0.1942540040 - 0.1225496913*I, v3=conjugate(v2)] and w1,2,3 are the roots of (-1-x^2+x^3): [w1=1.4655712319, w2=-0.2327856159 - 0.7925519925*I, w3=conjugate(w2)]. - _Gerry Martens_, Jun 27 2015

%e The number of compositions of 11 without any 1's and 2's is a(11-3) = a(8) = 13. The compositions are (11), (8,3), (3,8), (7,4), (4,7), (6,5), (5,6), (5,3,3), (3,5,3), (3,3,5), (4,4,3), (4,3,4), (3,4,4). - _Gregory L. Simay_, Jul 12 2016

%e The compositions from the above example may be mapped to the a(8) compositions of 8 into 1's and 3's using this (more generally applicable) method: replace all numbers greater than 3 with a 3 followed by 1's to make the same total, then remove the initial 3 from the composition. Maintaining the example's order, they become (1,1,1,1,1,1,1,1), (1,1,1,1,1,3), (3,1,1,1,1,1), (1,1,1,1,3,1), (1,3,1,1,1,1), (1,1,1,3,1,1), (1,1,3,1,1,1), (1,1,3,3), (3,1,1,3), (3,3,1,1), (1,3,1,3), (1,3,3,1), (3,1,3,1). - _Peter Munn_, May 31 2017

%p f := proc(r) local t1,i; t1 := []; for i from 1 to r do t1 := [op(t1),0]; od: for i from 1 to r+1 do t1 := [op(t1),1]; od: for i from 2*r+2 to 50 do t1 := [op(t1),t1[i-1]+t1[i-1-r]]; od: t1; end; # set r = order

%p with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 2)}, unlabeled]: seq(count(SeqSetU, size=j), j=3..40); # _Zerinvary Lajos_, Oct 10 2006

%p A000930 := proc(n)

%p add(binomial(n-2*k,k),k=0..floor(n/3)) ;

%p end proc: # _Zerinvary Lajos_, Apr 03 2007

%p a:= n-> (Matrix([[1,1,0],[0,0,1],[1,0,0]])^n)[1,1]: seq(a(n), n=0..50); # _Alois P. Heinz_, Jun 20 2008

%t a[0] = 1; a[1] = a[2] = 1; a[n_] := a[n] = a[n - 1] + a[n - 3]; Table[ a[n], {n, 0, 40} ]

%t CoefficientList[Series[1/(1-x-x^3), {x, 0, 45}], x] (* _Zerinvary Lajos_, Mar 22 2007 *)

%t LinearRecurrence[{1, 0, 1}, {1, 1, 1}, 80] (* _Vladimir Joseph Stephan Orlovsky_, Feb 11 2012 *)

%t a[n_] := HypergeometricPFQ[{(1-n)/3, (2-n)/3, -n/3}, {(1-n)/ 2, -n/2}, -27/4]; Table[a[n], {n, 0, 43}] (* _Jean-François Alcover_, Feb 26 2013 *)

%o (PARI) a(n)=polcoeff(exp(sum(m=1,n,((1+sqrt(1+4*x))^m + (1-sqrt(1+4*x))^m)*(x/2)^m/m)+x*O(x^n)),n) \\ _Paul D. Hanna_, Oct 08 2009

%o (PARI) x='x+O('x^66); Vec(1/(1-(x+x^3))) \\ _Joerg Arndt_, May 24 2011

%o (PARI) a(n)=([0,1,0;0,0,1;1,0,1]^n*[1;1;1])[1,1] \\ _Charles R Greathouse IV_, Feb 26 2017

%o (Maxima) makelist(sum(binomial(n-2*k,k),k,0,n/3),n,0,18); \\ _Emanuele Munarini_, May 24 2011

%o (Haskell)

%o a000930 n = a000930_list !! n

%o a000930_list = 1 : 1 : 1 : zipWith (+) a000930_list (drop 2 a000930_list)

%o -- _Reinhard Zumkeller_, Sep 25 2011

%o (MAGMA) [1,1] cat [ n le 3 select n else Self(n-1)+Self(n-3): n in [1..50] ]; // _Vincenzo Librandi_, Apr 25 2015

%o (GAP) a:=[1,1,1];; for n in [4..50] do a[n]:=a[n-1]+a[n-3]; od; a; # _Muniru A Asiru_, Aug 13 2018

%Y For Lamé sequences of orders 1 through 9 see A000045, this one, and A017898-A017904.

%Y Cf. A000073, A000213, A048715, A069241, A170954, A092526.

%Y See also A000079, A003269, A003520, A005708, A005709, A005710.

%Y Essentially the same as A068921 and A078012.

%Y See also A145580, A001609, A179070, A214551 (same rule except divide by gcd).

%Y A271901 and A271953 give the period of this sequence mod n.

%K nonn,easy,nice,changed

%O 0,4

%A _N. J. A. Sloane_

%E Name expanded by _N. J. A. Sloane_, Sep 07 2012

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 17 15:19 EST 2019. Contains 320220 sequences. (Running on oeis4.)