This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A000931 Padovan sequence (or Padovan numbers): a(n) = a(n-2) + a(n-3) with a(0)=1, a(1)=a(2)=0. (Formerly M0284 N0102) 225

%I M0284 N0102

%S 1,0,0,1,0,1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49,65,86,114,151,200,

%T 265,351,465,616,816,1081,1432,1897,2513,3329,4410,5842,7739,10252,

%U 13581,17991,23833,31572,41824,55405,73396,97229,128801,170625

%N Padovan sequence (or Padovan numbers): a(n) = a(n-2) + a(n-3) with a(0)=1, a(1)=a(2)=0.

%C Number of compositions of n into parts congruent to 2 mod 3 (offset -1). - _Vladeta Jovovic_, Feb 09 2005

%C a(n) = number of compositions of n into parts that are odd and >= 3. Example: a(10)=3 counts 3+7, 5+5, 7+3. - _David Callan_, Jul 14 2006

%C Referred to as N0102 in R. K. Guy's "Anyone for Twopins?" - _Rainer Rosenthal_, Dec 05 2006

%C Zagier conjectures that a(n+3) is the maximum number of multiple zeta values of weight n > 1 which are linearly independent over the rationals. - _Jonathan Sondow_ and Sergey Zlobin (sirg_zlobin(AT)mail.ru), Dec 20 2006

%C Starting with offset 6: (1, 1, 2, 2, 3, 4, 5, ...) = INVERT transform of A106510: (1, 1, -1, 0, 1, -1, 0, 1, -1, ...). - _Gary W. Adamson_, Oct 10 2008

%C Triangle A145462: right border = A000931 starting with offset 6. Row sums = Padovan sequence starting with offset 7. - _Gary W. Adamson_, Oct 10 2008

%C Starting with offset 3 = row sums of triangle A146973 and INVERT transform of [1, -1, 2, -2, 3, -3, ...]. - _Gary W. Adamson_, Nov 03 2008

%C a(n+5) corresponds to the diagonal sums of "triangle": 1; 1; 1,1; 1,1; 1,2,1; 1,2,1; 1,3,3,1; 1,3,3,1; 1,4,6,4,1; ..., rows of Pascal's triangle (A007318) repeated. - _Philippe Deléham_, Dec 12 2008

%C With offset 3: (1, 0, 1, 1, 1, 2, 2, ...) convolved with the tribonacci numbers prefaced with a "1": (1, 1, 1, 2, 4, 7, 13, ...) = the tribonacci numbers, A000073. (Cf. triangle A153462.) - _Gary W. Adamson_, Dec 27 2008

%C a(n) is also the number of strings of length (n-8) from an alphabet {A, B} with no more than one A or 2 B's consecutively. (E.g., n = 4: {ABAB,ABBA,BABA,BABB,BBAB} and a(4+8)= 5.) - _Toby Gottfried_, Mar 02 2010

%C p(n):=A000931(n+3), n >= 1, is the number of partitions of the numbers {1,2,3,...,n} into lists of length two or three containing neighboring numbers. The 'or' is inclusive. For n=0 one takes p(0)=1. For details see the W. Lang link. There the explicit formula for p(n) (analog of the Binet-de Moivre formula for Fibonacci numbers) is also given. Padovan sequences with different inputs are also considered there. - _Wolfdieter Lang_, Jun 15 2010

%C Equals the INVERTi transform of Fibonacci numbers prefaced with three 1's, i.e., (1 + x + x^2 + x^3 + x^4 + 2x^5 + 3x^6 + 5x^7 + 8x^8 + 13x^9 + ...). - _Gary W. Adamson_, Apr 01 2011

%C When run backwards gives (-1)^n*A050935(n).

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

%C Figure 4 of Brauchart et al., 2014, shows a way to "visualize the Padovan sequence as cuboid spirals, where the dimensions of each cuboid made up by the previous ones are given by three consecutive numbers in the sequence". - _N. J. A. Sloane_, Mar 26 2014

%C a(n) counts closed walks from a vertex of a unidirectional triangle containing an opposing directed edge (arc) between the second and third vertices. Equivalently the (1,1) entry of A^n where the adjacency matrix of digraph is A=(0,1,0;0,0,1;1,1,0). - _David Neil McGrath_, Dec 19 2014

%C Number of compositions of n-3 (n >= 4) into 2's and 3's. Example: a(12)=5 because we have 333, 3222, 2322, 2232, and 2223. - _Emeric Deutsch_, Dec 28 2014

%C The Hoffman (2015) paper "offers significant evidence that the number of quantities needed to generate the weight-n multiple harmonic sums mod p is" a(n). - _N. J. A. Sloane_, Jun 24 2016

%C a(n) gives the number of compositions of n-5 into odd parts where the order of the 1's does not matter. For example, a(11)=4 counts the following compositions of 6: (5,1)=(1,5), (3,3), (3,1,1,1)=(1,3,1,1)=(1,1,3,1)=(1,1,1,3), (1,1,1,1,1,1). - _Gregory L. Simay_, Aug 04 2016

%C For n > 6, a(n) is the number of maximal matchings in the (n-5)-path graph, maximal independent vertex sets and minimal vertex covers in the (n-6)-path graph, and minimal edge covers in the (n-5)-pan graph and (n-3)-path graphs. - _Eric W. Weisstein_, Mar 30, Aug 03, and Aug 07 2017

%C From _James Mitchell_ and _Wilf A. Wilson_, Jul 21 2017: (Start)

%C a(2n + 5) + 2n - 4, n > 2, is the number of maximal subsemigroups of the monoid of order-preserving mappings on a set with n elements.

%C a(n + 6) + n - 3, n > 3, is the number of maximal subsemigroups of the monoid of order-preserving or reversing mappings on a set with n elements.

%C (End)

%C If a sequence of nonnegative integers has the property that the largest of any four consecutive terms equals the sum of the two smallest then the sequence is either identically zero or merges with the present sequence or an integer multiple of it (such as A291289) after a finite number of steps". This must be a well-known property, and it would be nice to have a reference. - _N. J. A. Sloane_, Aug 29 2017

%C a(n) is also the number of maximal cliques in the (n+6)-path complement graph. - _Eric W. Weisstein_, Apr 12 2018

%D A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 47, ex. 4.

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

%D Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.

%D Hans van der Laan, Het plastische getal. XV lessen over de grondslagen van de architectonische ordonnantie. Leiden, E.J. Brill, 1967.

%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).

%D I. Stewart, Math. Rec., Scientific American, No. 6, 1996 p 102.

%D I. Stewart, L'univers des nombres, "La sculpture et les nombres", pp. 19-20, Belin-Pour La Science, Paris 2000.

%D D. Zagier, Values of zeta functions and their applications, in First European Congress of Mathematics (Paris, 1992), Vol. II, A. Joseph et al. (eds.), Birkhäuser, Basel, 1994, pp. 497-512.

%H Indranil Ghosh, <a href="/A000931/b000931.txt">Table of n, a(n) for n = 0..8180</a> (terms 0..1000 from T. D. Noe)

%H D. Applegate, M. LeBrun, N. J. A. Sloane, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Sloane/carry2.html">Dismal Arithmetic</a>, J. Int. Seq. 14 (2011) # 11.9.8.

%H C. Ballantine, M. Merca, <a href="http://dx.doi.org/10.1186/s13660-015-0952-5">Padovan numbers as sums over partitions into odd parts</a>, Journal of Inequalities and Applications, (2016) 2016:1. doi:10.1186/s13660-015-0952-5.

%H Barry Balof, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Balof/balof19.html">Restricted tilings and bijections</a>, J. Integer Seq. 15 (2012), no. 2, Article 12.2.3, 17 pp.

%H J.-L. Baril, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p178">Classical sequences revisited with permutations avoiding dotted pattern</a>, Electronic Journal of Combinatorics, 18 (2011), #P178.

%H J.-L. Baril, <a href="https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2343.1.html">Avoiding patterns in irreducible permutations</a>, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016). See Table 4.

%H Jean-Luc Baril, and Jean-Marcel Pallo, <a href="http://jl.baril.u-bourgogne.fr/filter.pdf">A Motzkin filter in the Tamari lattice</a>, Discrete Mathematics 338.8 (2015): 1370-1378.

%H Daniel Birmajer, Juan B. Gil, Michael D. Weiner, <a href="http://arxiv.org/abs/1505.06339">Linear recurrence sequences with indices in arithmetic progression and their sums</a>, arXiv preprint arXiv:1505.06339 [math.NT], 2015.

%H D. Birmajer, J. B. Gil, M. D. Weiner, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Gil/gil3.html">Linear Recurrence Sequences and Their Convolutions via Bell Polynomials</a>, Journal of Integer Sequences, 18 (2015), #15.1.2.

%H O. Bouillot, <a href="http://www.math.u-psud.fr/~bouillot/OB_The_Algebra_of_Multitangent_Functions.pdf">The Algebra of Multitangent Functions</a>, 2013

%H J. S. Brauchart, P. D. Dragnev, E. B. Saff, <a href="http://arxiv.org/abs/1402.3367">An Electrostatics Problem on the Sphere Arising from a Nearby Point Charge</a>, arXiv preprint arXiv:1402.3367 [math-ph], 2014. See Section 2, where the Padovan sequence is represented as a spiral of cubes (see Comments above). - _N. J. A. Sloane_, Mar 26 2014

%H F. Brown, <a href="http://arxiv.org/abs/1102.1310">On the decomposition of motivic multiple zeta values</a>, arXiv:1102.1310 [math.NT], 2011.

%H Minerva Catral, P. L. Ford, P. E. Harris, S. J. Miller, et al., <a href="https://arxiv.org/abs/1606.09312">Legal Decompositions Arising from Non-positive Linear Recurrences</a>, arXiv preprint arXiv:1606.09312 [math.CO], 2016.

%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 Moshe Cohen, <a href="http://arxiv.org/abs/1409.6614">The Jones polynomials of 3-bridge knots via Chebyshev knots and billiard table diagrams</a>, arXiv preprint arXiv:1409.6614 [math.GT], 2014.

%H Tomislav Doslic, I. Zubac, <a href="http://amc-journal.eu/index.php/amc/article/view/851">Counting maximal matchings in linear polymers</a>, Ars Mathematica Contemporanea 11 (2016) 255-276.

%H James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson <a href="https://arxiv.org/abs/1706.04967">Maximal subsemigroups of finite transformation and partition monoids</a>, arXiv:1706.04967 [math.GR], 2017. [From _James Mitchell_ and _Wilf A. Wilson_, Jul 21 2017]

%H Aysel Erey, Zachary Gershkoff, Amanda Lohss, Ranjan Rohatgi, <a href="https://arxiv.org/abs/1709.06979">Characterization and enumeration of 3-regular permutation graphs</a>, arXiv:1709.06979 [math.CO], 2017.

%H Reinhardt Euler, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Euler/euler1.html">The Fibonacci Number of a Grid Graph and a New Class of Integer Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.6.

%H R. Euler, P. Oleksik, Z. Skupien, <a href="http://dx.doi.org/10.7151/dmgt.1707">Counting Maximal Distance-Independent Sets in Grid Graphs</a>, Discussiones Mathematicae Graph Theory. Volume 33, Issue 3, Pages 531-557, ISSN (Print) 2083-5892, DOI: 10.7151/dmgt.1707, July 2013.

%H P. Flajolet and B. Salvy, <a href="http://projecteuclid.org/euclid.em/1047674270">Euler Sums and Contour Integral Representations</a>, Experimental Mathematics Vol. 7 issue 1 (1998)

%H D. Gerdemann <a href="http://www.youtube.com/watch?v=Q43AqMY90AI">Sums of Padovan numbers equal to sums of powers of plastic number (YouTube video)</a>

%H J. B. Gil, M. D. Weiner & C. Zara, <a href="http://arXiv.org/abs/math/0605348">Complete Padovan sequences in finite fields</a>, arXiv:math/0605348 [math.NT], 2006.

%H Juan B. Gil, Michael D. Weiner and Catalin Zara, <a href="http://www.fq.math.ca/Papers1/45-1/quartgil01_2007.pdf">Complete Padovan sequences in finite fields</a>, The Fibonacci Quarterly, vol. 45 (Feb 2007 issue), pp. 64 - 75.

%H N. Gogin and A. Mylläri, <a href="http://www.aca2013.uma.es/Proceedings.pdf#page=184">Padovan-like sequences and Bell polynomials</a>, Proceedings of Applications of Computer Algebra ACA, 2013.

%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 Tony Grubman and Ian M. Wanless, <a href="http://dx.doi.org/10.1016/j.jcta.2013.11.006">Growth rate of canonical and minimal group embeddings of spherical latin trades</a>, Journal of Combinatorial Theory, Series A, 2014, 57-72.

%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 Rachel Hall, <a href="http://www.sju.edu/~rhall/Rhythms/poets.pdf">Math for Poets and Drummers</a>.

%H Michael E. Hoffman, <a href="http://doi.org/10.2206/kyushujm.69.345">Quasi-symmetric functions and mod p multiple harmonic sums</a>, Kyushu Journal of Mathematics, Vol. 69 (2015) No. 2 p. 345-366.

%H Milan Janjić, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Janjic/janjic93.html">Words and Linear Recurrences</a>, J. Int. Seq. 21 (2018), #18.1.4.

%H Paul Johnson, <a href="https://arxiv.org/abs/1802.09621">Simultaneous cores with restrictions and a question of Zaleski and Zeilberger</a>, arXiv:1802.09621 [math.CO], 2018.

%H A. Ilic, S. Klavzar and Y. Rho, <a href="http://www.fmf.uni-lj.si/~klavzar/preprints/BalancedFibo-submit.pdf">Parity index of binary words and powers of prime words</a>, 2012. - _N. J. A. Sloane_, Sep 27 2012

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=393">Encyclopedia of Combinatorial Structures 393</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. 90.

%H Virginia Johnson, C. K. Cook, <a href="https://arxiv.org/abs/1608.02420">Areas of Triangles and other Polygons with Vertices from Various Sequences</a>, arXiv preprint arXiv:1608.02420 [math.CO], 2016.

%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 W. Lang, <a href="http://www.itp.kit.edu/~wl/EISpub/A000931.text"> Padovan combinatorics, explicit formula, and sequences with various inputs.</a> - _Wolfdieter Lang_, Jun 15 2010

%H J. M. Luck, A. Mehta, <a href="http://arxiv.org/abs/1511.04340">Universality in survivor distributions: Characterising the winners of competitive dynamics</a>, arXiv preprint arXiv:1511.04340 [q-bio.QM], 2015.

%H R. J. Mathar, <a href="http://arxiv.org/abs/1311.6135">Paving rectangular regions with rectangular tiles,....</a>, arXiv:1311.6135 [math.CO], 2013, see Table 49.

%H R. Mullen, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Mullen/mullen2.html">On Determining Paint by Numbers Puzzles with Nonunique Solutions</a>, JIS 12 (2009) 09.6.5

%H Wilbert Osmond, <a href="http://cys.or.id/docs/icys2014_abstract_wilbert_osmond.pdf">Growing Trees in Padovan Sequence For The Enhancement of L-System Algorithm</a>, 2014.

%H Richard Padovan, <a href="https://www.nexusjournal.com/the-nexus-conferences/nexus-2002/148-n2002-padovan.html">Dom Hans Van Der Laan And The Plastic Number</a>, pp. 181-193 in Nexus IV: Architecture and Mathematics, eds. Kim Williams and Jose Francisco Rodrigues, Fucecchio (Florence): Kim Williams Books, 2002.

%H Richard Padovan, <a href="https://link.springer.com/chapter/10.1007/978-3-319-00143-2_27">Dom Hans van der Laan and the Plastic Number</a>, Chapter 74, pp 407-419, Volume II of K. Williams and M.J. Ostwald (eds.), Architecture and Mathematics from Antiquity to the Future, DOI 10.1007/978-3-319-00143-2_27, Springer International Publishing Switzerland 2015.

%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 S. Saito, T. Tanaka, N. Wakabayashi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Saito/saito22.html">Combinatorial Remarks on the Cyclic Sum Formula for Multiple Zeta Values </a>, J. Int. Seq. 14 (2011) # 11.2.4, Conjecture 2.

%H I. Stewart, <a href="http://www.fortunecity.com/emachines/e11/86/padovan.html">Tales of a Neglected Number</a>

%H M. Waldschmidt, <a href="http://www.math.jussieu.fr/~miw/articles/pdf/MZV2011IMSc.pdf">Lectures on Multiple Zeta Values</a> (IMSC 2011).

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalClique.html">Maximal Clique</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalIndependentVertexSet.html">Maximal Independent Vertex Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimalEdgeCover.html">Minimal Edge Cover</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimalVertexCover.html">Minimal Vertex Cover</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PanGraph.html">Pan Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PathComplementGraph.html">Path Complement Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PathGraph.html">Path Graph</a>

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

%H I. Wloch, U. Bednarz, D. Bród, A Wloch and M. Wolowiec-Musial, <a href="http://dx.doi.org/10.1016/j.dam.2013.05.029">On a new type of distance Fibonacci numbers</a>, Discrete Applied Math., Volume 161, Issues 16-17, November 2013, Pages 2695-2701.

%H R. Yanco, <a href="/A007380/a007380.pdf">Letter and Email to N. J. A. Sloane, 1994</a>

%H R. Yanco and A. Bagchi, <a href="/A007380/a007380_1.pdf">K-th order maximal independent sets in path and cycle graphs</a>, Unpublished manuscript, 1994. (Annotated scanned copy)

%H S. Zlobin, <a href="http://arXiv.org/abs/math/0601151">A note on arithmetic properties of multiple zeta values</a>, arXiv:math/0601151 [math.NT], 2006.

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

%F G.f.: (1-x^2)/(1-x^2-x^3).

%F a(n) is asymptotic to r^n / (2*r+3) where r = 1.3247179572447... = A060006, the real root of x^3 = x + 1. - _Philippe Deléham_, Jan 13 2004

%F a(n)^2 + a(n+2)^2 + a(n+6)^2 = a(n+1)^2 + a(n+3)^2 + a(n+4)^2 + a(n+5)^2 (Barniville, Question 16884, Ed. Times 1911).

%F a(n+5) = a(0) + a(1) + ... + a(n).

%F a(n) = central and lower right terms in the (n-3)-th power of the 3 X 3 matrix M = [0 1 0 / 0 0 1 / 1 1 0]. E.g., a(13) = 7. M^10 = [3 5 4 / 4 7 5 / 5 9 7]. - _Gary W. Adamson_, Feb 01 2004

%F G.f.: 1/(1 - x^3 - x^5 - x^7 - x^9 - ...). - _Jon Perry_, Jul 04 2004

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

%F a(n) = Sum_{k=0..floor(n/2)} binomial(k, n-2k). - _Paul Barry_, Sep 17 2004

%F a(n+3) is diagonal sum of A026729 (as a number triangle), with formula a(n+3) = Sum_{k=0..floor(n/2)} Sum_{i=0..n-k} (-1)^(n-k+i)*binomial(n-k, i)*binomial(i+k, i-k). - _Paul Barry_, Sep 23 2004

%F a(n) = a(n-1) + a(n-5) = A003520(n-4) + A003520(n-13) = A003520(n-3) - A003520(n-9). - _Henry Bottomley_, Jan 30 2005

%F a(n+3) = Sum_{k=0..floor(n/2)} binomial((n-k)/2, k)(1+(-1)^(n-k))/2. - _Paul Barry_, Sep 09 2005

%F The sequence 1/(1-x^2-x^3) (a(n+3)) is given by the diagonal sums of the Riordan array (1/(1-x^3), x/(1-x^3)). The row sums are A000930. - _Paul Barry_, Feb 25 2005

%F a(n) = A023434(n-7) + 1 for n >= 7. - _David Callan_, Jul 14 2006

%F a(n+5) corresponds to the diagonal sums of A030528. The binomial transform of a(n+5) is A052921. a(n+5) = Sum_{k=0..floor(n/2)} Sum_{k=0..n} (-1)^(n-k+i)binomial(n-k, i)binomial(i+k+1, 2k+1). - _Paul Barry_, Jun 21 2004

%F r^(n-1) = (1/r)*a(n) + r*(n+1) + a(n+2), where r = 1.32471... is the real root of x^3 - x - 1 = 0. Example: r^8 = (1/r)*a(9) + r*a(10) + a(11) = ((1/r)*2 + r*3 + 4 = 9.483909... - _Gary W. Adamson_, Oct 22 2006

%F a(n) = (r^n)/(2r+3) + (s^n)/(2s+3) + (t^n)/(2t+3) where r, s, t are the three roots of x^3-x-1. - Keith Schneider (schneidk(AT)email.unc.edu), Sep 07 2007

%F a(n) = -k*a(n-1) + a(n-2) + (k+1)a(n-2) + k*a(n-4), n > 3, for any value of k. - _Gary Detlefs_, Sep 13 2010

%F From _Francesco Daddi_, Aug 04 2011: (Start)

%F a(0) + a(2) + a(4) + a(6) + ... + a(2*n) = a(2*n+3).

%F a(0) + a(3) + a(6) + a(9) + ... + a(3*n) = a(3*n+2)+1.

%F a(0) + a(5) + a(10) + a(15) + ... + a(5*n) = a(5*n+1)+1.

%F a(0) + a(7) + a(14) + a(21) + ... + a(7*n) = (a(7*n) + a(7*n+1) + 1)/2. (End)

%F a(n+3) = Sum_{k=0..floor((n+1)/2)} binomial((n+k)/3,k), where binomial((n+k)/3,k)=0 for noninteger (n+k)/3. - _Nikita Gogin_, Dec 07 2012

%F a(n) = A182097(n-3) for n > 2. - _Jonathan Sondow_, Mar 14 2014

%F a(n) = the k-th difference of a(n+5k) - a(n+5k-1), k>=1. For example, a(10)=3 => a(15)-a(14) => 2nd difference of a(20)-a(19) => 3rd difference of a(25)-a(24)... - _Bob Selcoe_, Mar 18 2014

%F Construct the power matrix T(n,j) = [A^*j]*[S^*(j-1)] where A=(0,0,1,0,1,0,1,...) and S=(0,1,0,0,...) or A063524. [* is convolution operation] Define S^*0=I with I=(1,0,0,...). Then a(n) = Sum_{j=1...n} T(n,j). - _David Neil McGrath_, Dec 19 2014

%F If x=a(n), y=a(n+1), z=a(n+2), then x^3 + 2*y*x^2 - z^2*x - 3*y*z*x + y^2*x + y^3 - y^2*z + z^3 = 1. - _Alexander Samokrutov_, Jul 20 2015

%F For the sequence shifted by 6 terms, a(n) = Sum( binomial(k+1,3*k-n), k=ceiling(n/3)..ceiling(n/2)) [Doslic-Zubac]. - _N. J. A. Sloane_, Apr 23 2017

%e G.f. = 1 + x^3 + x^5 + x^6 + x^7 + 2*x^8 + 2*x^9 + 3*x^10 + 4*x^11 + ...

%p A000931 := proc(n) option remember; if n = 0 then 1 elif n <= 2 then 0 else procname(n-2)+procname(n-3); fi; end;

%p A000931:=-(1+z)/(-1+z^2+z^3); # _Simon Plouffe_ in his 1992 dissertation; gives sequence without five leading terms

%p a[0]:=1; a[1]:=0; a[2]:=0; for n from 3 to 50 do a[n]:=a[n-2]+a[n-3]; end do; # _Francesco Daddi_, Aug 04 2011

%t CoefficientList[Series[(1 - x^2)/(1 - x^2 - x^3), {x, 0, 50}], x]

%t a[0] = 1; a[1] = a[2] = 0; a[n_] := a[n] = a[n - 2] + a[n - 3]; Table[a[n], {n, 0, 51}] (* _Robert G. Wilson v_, May 04 2006 *)

%t LinearRecurrence[{0, 1, 1}, {1, 0, 0}, 50] (* _Harvey P. Dale_, Jan 10 2012 *)

%t Table[RootSum[-1 - # + #^3 &, 5 #^n - 6 #^(n + 1) + 4 #^(n + 2) &]/23, {n, 0, 20}] (* _Eric W. Weisstein_, Nov 09 2017 *)

%o a000931 n = a000931_list !! n

%o a000931_list = 1 : 0 : 0 : zipWith (+) a000931_list (tail a000931_list)

%o -- _Reinhard Zumkeller_, Feb 10 2011

%o (PARI) Vec((1-x^2)/(1-x^2-x^3)+O(x^99)) \\ _Charles R Greathouse IV_, Feb 11 2011

%o (PARI) {a(n) = if( n<0, polcoeff( 1 / (1 + x - x^3) + x * O(x^-n), -n), polcoeff( (1 - x^2) / (1 - x^2 - x^3) + x * O(x^n), n))}; /* _Michael Somos_, Sep 18 2012 */

%o (MAGMA) I:=[1,0,0]; [n le 3 select I[n] else Self(n-2) + Self(n-3): n in [1..60]]; // _Vincenzo Librandi_, Jul 21 2015

%Y The following are basically all variants of the same sequence: A000931, A078027, A096231, A124745, A133034, A134816, A164001, A182097, A228361 and probably A020720. However, each one has its own special features and deserves its own entry.

%Y Closely related to A001608.

%Y Cf. A000073, A005682-A005691, A103372-A103380, A106510, A145462, A146973, A153462, A291289.

%Y Doubling every term gives A291289.

%K nonn,easy,nice

%O 0,9

%A _N. J. A. Sloane_

%E Edited by _Charles R Greathouse IV_, Mar 17 2010

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.

Last modified June 25 13:09 EDT 2018. Contains 311907 sequences. (Running on oeis4.)