# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a000931
Showing 1-1 of 1
%I A000931 M0284 N0102 #640 Oct 24 2024 12:33:20
%S A000931 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 A000931 265,351,465,616,816,1081,1432,1897,2513,3329,4410,5842,7739,10252,
%U A000931 13581,17991,23833,31572,41824,55405,73396,97229,128801,170625
%N A000931 Padovan sequence (or Padovan numbers): a(n) = a(n-2) + a(n-3) with a(0) = 1, a(1) = a(2) = 0.
%C A000931 Number of compositions of n into parts congruent to 2 mod 3 (offset -1). - _Vladeta Jovovic_, Feb 09 2005
%C A000931 a(n) is the 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 A000931 Referred to as N0102 in R. K. Guy's "Anyone for Twopins?" - _Rainer Rosenthal_, Dec 05 2006
%C A000931 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 A000931 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 A000931 Starting with offset 7, the sequence 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, ... is called the Fibonacci quilt sequence by Catral et al., in Fib. Q. 2017. - _N. J. A. Sloane_, Dec 24 2021
%C A000931 Triangle A145462: right border = A000931 starting with offset 6. Row sums = Padovan sequence starting with offset 7. - _Gary W. Adamson_, Oct 10 2008
%C A000931 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 A000931 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 A000931 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 A000931 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 A000931 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 A000931 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 A000931 When run backwards gives (-1)^n*A050935(n).
%C A000931 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 A000931 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 A000931 a(n) is the number of 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 A000931 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 A000931 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 A000931 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 A000931 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 A000931 From _James Mitchell_ and _Wilf A. Wilson_, Jul 21 2017: (Start)
%C A000931 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 A000931 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 A000931 (End)
%C A000931 Has the property that the largest of any four consecutive terms equals the sum of the two smallest. - _N. J. A. Sloane_, Aug 29 2017 [_David Nacin_ points out that there are many sequences with this property, such as 1,1,1,2,1,1,1,2,1,1,1,2,... or 2,3,4,5,2,3,4,5,2,3,4,5,... or 2,2,1,3,3, 4,1,4, 5,5,1,6,6, 7,1,7, 8,8,1,9,9, 10,1,10, ... (spaces added for clarity), and a conjecture I made here in 2017 was simply wrong. I have deleted it. - _N. J. A. Sloane_, Oct 23 2018]
%C A000931 a(n) is also the number of maximal cliques in the (n+6)-path complement graph. - _Eric W. Weisstein_, Apr 12 2018
%C A000931 a(n+8) is the number of solus bitstrings of length n with no runs of 3 zeros. - _Steven Finch_, Mar 25 2020
%C A000931 Named after the architect Richard Padovan (b. 1935). - _Amiram Eldar_, Jun 08 2021
%C A000931 Shannon et al. (2006) credit a French architecture student Gérard Cordonnier with the discovery of these numbers.
%C A000931 For n >= 3, a(n) is the number of sequences of 0s and 1s of length (n-2) that begin with a 0, end with a 0, contain no two consecutive 0s, and contain no three consecutive 1s. - _Yifan Xie_, Oct 20 2022
%C A000931 For n >= 2, a(n+5) is the number of ways to tile the 1xn board with dominoes and squares (ie. size 1x1) such that are either none or one squares between dominoes, none or one squares at both ends of the board, and there is at least one domino. For example, for n=6, a(11)=4 since the tilings are |2|2, |22|, 2|2| and 222 (where 2 represents a domino and | a square). - _Enrique Navarrete_, Aug 31 2024
%D A000931 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 A000931 Minerva Catral, Pari L. Ford, Pamela E. Harris, Steven J. Miller, Dawn Nelson, Zhao Pan, and Huanzhong Xu, Legal Decompositions Arising from Non-positive Linear Recurrences, Fib. Quart., 55:3 (2017), 252-275. [Note that there is an earlier version of this paper, with only five authors, on the arXiv in 2016. Note to editors: do not merge these two citations. - _N. J. A. Sloane_, Dec 24 2021]
%D A000931 Richard K. Guy, "Anyone for Twopins?" in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 10-11.
%D A000931 Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
%D A000931 A. G. Shannon, P. G. Anderson and A. F. Horadam, Properties of Cordonnier, Perrin and Van der Laan numbers, International Journal of Mathematical Education in Science and Technology, Volume 37:7 (2006), 825-831. See P_n.
%D A000931 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000931 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A000931 Ian Stewart, L'univers des nombres, "La sculpture et les nombres", pp. 19-20, Belin-Pour La Science, Paris, 2000.
%D A000931 Steven J. Tedford, Combinatorial identities for the Padovan numbers, Fib. Q., Vol. 57, No. 4 (2019), pp. 291-298.
%D A000931 Hans van der Laan, Het plastische getal. XV lessen over de grondslagen van de architectonische ordonnantie. Leiden, E.J. Brill, 1967.
%D A000931 Don 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 A000931 Indranil Ghosh, Table of n, a(n) for n = 0..8180 (terms 0..1000 from T. D. Noe)
%H A000931 Kouèssi Norbert Adédji, Japhet Odjoumani, and Alain Togbé, Padovan and Perrin numbers as products of two generalized Lucas numbers, Archivum Mathematicum, Vol. 59 (2023), No. 4, 315-337.
%H A000931 David Applegate, Marc LeBrun and N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
%H A000931 Andrei Asinowski, Cyril Banderier and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
%H A000931 Mohamadou Bachabi and Alain S. Togbé, Products of Fermat or Mersenne numbers in some sequences, Math. Comm. (2024) Vol. 29, 265-285.
%H A000931 Cristina Ballantine and Mircea Merca, Padovan numbers as sums over partitions into odd parts, Journal of Inequalities and Applications, (2016) 2016:1. doi:10.1186/s13660-015-0952-5.
%H A000931 Barry Balof, Restricted tilings and bijections, J. Integer Seq., Vol. 15, No. 2 (2012), Article 12.2.3, 17 pp.
%H A000931 Jean-Luc Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, Vol. 18, No. 1 (2011), #P178.
%H A000931 Jean-Luc Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol. 17, No. 3 (2016), pp. 13-30. See Table 4.
%H A000931 Jean-Luc Baril and Jean-Marcel Pallo, A Motzkin filter in the Tamari lattice, Discrete Mathematics, Vol. 338, No. 8 (2015), pp. 1370-1378.
%H A000931 Daniel Birmajer, Juan B. Gil and Michael D. Weiner, Linear recurrence sequences with indices in arithmetic progression and their sums, arXiv preprint arXiv:1505.06339 [math.NT], 2015.
%H A000931 Daniel Birmajer, Juan B. Gil and Michael D. Weiner, Linear Recurrence Sequences and Their Convolutions via Bell Polynomials, Journal of Integer Sequences, Vol. 18 (2015), #15.1.2.
%H A000931 Khadidja Boubellouta and Mohamed Kerada, Some Identities and Generating Functions for Padovan Numbers, Tamap Journal of Mathematics and Statistics (2019), Article SI04.
%H A000931 Olivier Bouillot, The Algebra of Multitangent Functions, arXiv:1404.0992 [math.NT], 2014.
%H A000931 Johann S. Brauchart, Peter D. Dragnev and Edward B. Saff, An Electrostatics Problem on the Sphere Arising from a Nearby Point Charge, 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 A000931 Ulrich Brenner, Anna Hermann and Jannik Silvanus, Constructing Depth-Optimum Circuits for Adders and AND-OR Paths, arXiv:2012.05550 [cs.DM], 2020.
%H A000931 D. J. Broadhurst and D. Kreimer, Association of multiple zeta values with positive knots via Feynman diagrams up to 9 loops, Phys. Lett B., Vol. 393, No. 3-4 (1997), pp. 403-412. UTA-PHYS-96-44; arXiv preprint, arXiv:hep-th/9609128, 1996. Table 1 K_n.
%H A000931 Francis Brown, On the decomposition of motivic multiple zeta values, arXiv:1102.1310 [math.NT], 2011.
%H A000931 Minerva Catral, Pari L. Ford, Pamela E. Harris, Steven J. Miller and Dawn Nelson, Legal Decompositions Arising from Non-positive Linear Recurrences, arXiv preprint arXiv:1606.09312 [math.CO], 2016. [Note that there is a 2017 paper in the Fib. Quart. with the same title but with seven authors - see References above. -_N. J. A. Sloane_, Dec 24 2021]
%H A000931 Frédéric Chapoton, Multiple T-values with one parameter, arXiv:2108.08534 [math.NT], 2021. See p. 5.
%H A000931 Phyllis Chinn and Silvia Heubach, Integer Sequences Related to Compositions without 2's, J. Integer Seqs., Vol. 6 (2003), Article 03.2.3.
%H A000931 Moshe Cohen, The Jones polynomials of 3-bridge knots via Chebyshev knots and billiard table diagrams, arXiv preprint arXiv:1409.6614 [math.GT], 2014.
%H A000931 Mahadi Ddamulira, On the x-coordinates of Pell equations which are sums of two Padovan numbers, arXiv:1905.11322 [math.NT], 2019.
%H A000931 Mahadi Ddamulira, Padovan numbers that are concatenations of two repdigits, arXiv:2003.10705 [math.NT], 2020.
%H A000931 Mahadi Ddamulira, On the x-coordinates of Pell equations that are products of two Padovan numbers, Integers: Electronic Journal of Combinatorial Number Theory, State University of West Georgia, Charles University, and DIMATIA (2020), hal-02471858.
%H A000931 Mahadi Ddamulira, Padovan numbers that are concatenations of two distinct repdigits, arXiv:2003.10705 [math.NT], 2020.
%H A000931 Mahadi Ddamulira, Padovan numbers that are concatenations of two distinct repdigits, Cambridge Open Engage (2020), preprint.
%H A000931 Mahadi Ddamulira, On the x-coordinates of Pell Equations that are Products of Two Padovan Numbers, Integers (2020) Vol. 20, #A70.
%H A000931 Tomislav Doslic and I. Zubac, Counting maximal matchings in linear polymers, Ars Mathematica Contemporanea, Vol. 11 (2016), pp. 255-276.
%H A000931 James East, Jitender Kumar, James D. Mitchell and Wilf A. Wilson, Maximal subsemigroups of finite transformation and partition monoids, arXiv:1706.04967 [math.GR], 2017. [From _James Mitchell_ and _Wilf A. Wilson_, Jul 21 2017]
%H A000931 Aysel Erey, Zachary Gershkoff, Amanda Lohss and Ranjan Rohatgi, Characterization and enumeration of 3-regular permutation graphs, arXiv:1709.06979 [math.CO], 2017.
%H A000931 Reinhardt Euler, The Fibonacci Number of a Grid Graph and a New Class of Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.6.
%H A000931 Reinhardt Euler, Paweł Oleksik and Zdzisław Skupien, Counting Maximal Distance-Independent Sets in Grid Graphs, Discussiones Mathematicae Graph Theory, Vol. 33, No. 3 (2013), pp. 531-557, ISSN (Print) 2083-5892.
%H A000931 Sergio Falcón, Binomial Transform of the Generalized k-Fibonacci Numbers, Communications in Mathematics and Applications, Vol. 10, No. 3 (2019), pp. 643-651.
%H A000931 Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.
%H A000931 Philippe Flajolet and Bruno Salvy, Euler Sums and Contour Integral Representations, Experimental Mathematics, Vol. 7, No. 1 (1998), pp. 15-35.
%H A000931 Dale Gerdemann, Sums of Padovan numbers equal to sums of powers of plastic number, YouTube video.
%H A000931 Dale Gerdemann, Tuba Fantasy (music generated from Padovan numbers), YouTube video.
%H A000931 Juan B. Gil, Michael D. Weiner and Catalin Zara, Complete Padovan sequences in finite fields, arXiv:math/0605348 [math.NT], 2006.
%H A000931 Juan B. Gil, Michael D. Weiner and Catalin Zara, Complete Padovan sequences in finite fields, The Fibonacci Quarterly, Vol. 45, No. 1 (Feb 2007), pp. 64-75.
%H A000931 N. Gogin and A. Mylläri, Padovan-like sequences and Bell polynomials, Proceedings of Applications of Computer Algebra ACA, 2013.
%H A000931 Taras Goy, Some families of identities for Padovan numbers, Proc. Jangjeon Math. Soc., Vol. 21, No. 3 (2018), pp. 413-419.
%H A000931 Taras Goy and Mark Shattuck, Determinant Identities for Toeplitz-Hessenberg Matrices with Tribonacci Number Entries, arXiv:2003.10660 [math.CO], 2020.
%H A000931 T. M. Green, Recurrent sequences and Pascal's triangle, Math. Mag., Vol. 41, No. 1 (1968), pp. 13-21.
%H A000931 Tony Grubman and Ian M. Wanless, Growth rate of canonical and minimal group embeddings of spherical latin trades, Journal of Combinatorial Theory, Series A, 2014, 57-72.
%H A000931 Richard K. Guy, Anyone for Twopins?, in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15. [Annotated scanned copy, with permission]
%H A000931 Rachel Wells Hall, Math for Poets and Drummers, Math Horizons, Vol. 15, No. 3 (2008), pp. 10-24; preprint; Wayback Machine link.
%H A000931 Michael E. Hoffman, Quasi-symmetric functions and mod p multiple harmonic sums, Kyushu Journal of Mathematics, Vol. 69, No. 2 (2015), pp. 345-366.
%H A000931 Svenja Huntemann and Neil A. McKay, Counting Domineering Positions, arXiv:1909.12419 [math.CO], 2019.
%H A000931 Aleksandar Ilić, Sandi Klavžar, and Yoomi Rho, Parity index of binary words and powers of prime words, The electronic journal of combinatorics, Vol. 19, No. 3 (2012), #P44. - _N. J. A. Sloane_, Sep 27 2012
%H A000931 INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 393.
%H A000931 Milan Janjic, Recurrence Relations and Determinants, arXiv preprint arXiv:1112.2466 [math.CO], 2011.
%H A000931 Milan Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, Vol. 15 (2012), Article 12.3.5.
%H A000931 Milan Janjić, Words and Linear Recurrences, J. Int. Seq., Vol. 21 (2018), Article 18.1.4.
%H A000931 Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 90.
%H A000931 Paul Johnson, Simultaneous cores with restrictions and a question of Zaleski and Zeilberger, arXiv:1802.09621 [math.CO], 2018.
%H A000931 Virginia Johnson and C. K. Cook, Areas of Triangles and other Polygons with Vertices from Various Sequences, arXiv preprint arXiv:1608.02420 [math.CO], 2016.
%H A000931 Vedran Krcadinac, A new generalization of the golden ratio, Fibonacci Quart., Vol. 44, No. 4 (2006), pp. 335-340.
%H A000931 Wolfdieter Lang, Padovan combinatorics, explicit formula, and sequences with various inputs. - _Wolfdieter Lang_, Jun 15 2010
%H A000931 Ana Cecilia García Lomelí and Santos Hernández Hernández, Repdigits as Sums of Two Padovan Numbers, J. Int. Seq., Vol. 22 (2019), Article 19.2.3.
%H A000931 J. M. Luck and A. Mehta, Universality in survivor distributions: Characterising the winners of competitive dynamics, arXiv preprint arXiv:1511.04340 [q-bio.QM], 2015.
%H A000931 R. J. Mathar, Paving Rectangular Regions with Rectangular Tiles: Tatami and Non-Tatami Tilings, arXiv:1311.6135 [math.CO], 2013, see Table 49.
%H A000931 Steven J. Miller and Alexandra Newlon, The Fibonacci Quilt Game, arXiv preprint arXiv:1909.01938 [math.NT], 2019. Also Fib. Q., Vol. 58, No. 2 (2020), pp. 157-168. (See Fig. 2, The "Fibonacci Quilt" sequence.)
%H A000931 Ryan Mullen, On Determining Paint by Numbers Puzzles with Nonunique Solutions, JIS, Vol. 12 (2009), Article 09.6.5.
%H A000931 Mariana Nagy, Simon R. Cowell and Valeriu Beiu, Survey of Cubic Fibonacci Identities - When Cuboids Carry Weight, arXiv:1902.05944 [math.HO], 2019.
%H A000931 Wilbert Osmond, Growing Trees in Padovan Sequence For The Enhancement of L-System Algorithm, 2014.
%H A000931 Richard Padovan, Dom Hans Van Der Laan And The Plastic Number, pp. 181-193 in Nexus IV: Architecture and Mathematics, eds. Kim Williams and Jose Francisco Rodrigues, Fucecchio (Florence): Kim Williams Books, 2002.
%H A000931 Richard Padovan, Dom Hans van der Laan and the Plastic Number, 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 A000931 Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A000931 Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
%H A000931 Narad Rampersad and Max Wiebe, Sums of products of binomial coefficients mod 2 and 2-regular sequences, Integers (2024) Vol. 24, Art. No. A73. See p. 11.
%H A000931 Salah Eddine Rihane, Chèfiath Awero Adegbindin and Alain Togbé, Fermat Padovan And Perrin Numbers, J. Int. Seq., Vol. 23 (2020), Article 20.6.2.
%H A000931 Shingo Saito, Tatsushi Tanaka and Noriko Wakabayashi, Combinatorial Remarks on the Cyclic Sum Formula for Multiple Zeta Values, J. Int. Seq., Vol. 14 (2011), Article 11.2.4, Conjecture 2.
%H A000931 Ian Stewart, Tales of a Neglected Number, Mathematical Recreations, Scientific American, Vol. 274, No. 6 (1996), pp. 102-103.
%H A000931 Michel Waldschmidt, Lectures on Multiple Zeta Values (IMSC 2011).
%H A000931 Eric Weisstein's World of Mathematics, Maximal Clique.
%H A000931 Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set.
%H A000931 Eric Weisstein's World of Mathematics, Minimal Edge Cover.
%H A000931 Eric Weisstein's World of Mathematics, Minimal Vertex Cover.
%H A000931 Eric Weisstein's World of Mathematics, Padovan Sequence.
%H A000931 Eric Weisstein's World of Mathematics, Pan Graph.
%H A000931 Eric Weisstein's World of Mathematics, Path Complement Graph.
%H A000931 Eric Weisstein's World of Mathematics, Path Graph.
%H A000931 Erv Wilson, The Scales of Mt. Meru.
%H A000931 Iwona Włoch, Urszula Bednarz, Dorota Bród, Andrzej Włoch and Małgorzata Wołowiec-Musiał, On a new type of distance Fibonacci numbers, Discrete Applied Math., Vol. 161, No. 16-17 (November 2013) pp. 2695-2701.
%H A000931 Richard Yanco, Letter and Email to N. J. A. Sloane, 1994.
%H A000931 Richard Yanco and Ansuman Bagchi, K-th order maximal independent sets in path and cycle graphs, Unpublished manuscript, 1994. (Annotated scanned copy)
%H A000931 Diyar O. Mustafa Zangana and Ahmet Öteleş, Padovan Numbers by the Permanents of a Certain Complex Pentadiagonal Matrix, J. of Garmian Univ., Vol. 5, No. 2 (2018), pp. 330-338.
%H A000931 Sergey Zlobin, A note on arithmetic properties of multiple zeta values, arXiv:math/0601151 [math.NT], 2006.
%H A000931 Index entries for linear recurrences with constant coefficients, signature (0,1,1).
%F A000931 G.f.: (1-x^2)/(1-x^2-x^3).
%F A000931 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 A000931 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 A000931 a(n+5) = a(0) + a(1) + ... + a(n).
%F A000931 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 A000931 G.f.: 1/(1 - x^3 - x^5 - x^7 - x^9 - ...). - _Jon Perry_, Jul 04 2004
%F A000931 a(n+4) = Sum_{k=0..floor((n-1)/2)} binomial(floor((n+k-2)/3), k). - _Paul Barry_, Jul 06 2004
%F A000931 a(n+3) = Sum_{k=0..floor(n/2)} binomial(k, n-2k). - _Paul Barry_, Sep 17 2004, corrected by _Greg Dresden_ and _Zi Ye_, Jul 06 2021
%F A000931 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 A000931 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 A000931 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 A000931 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 A000931 a(n) = A023434(n-7) + 1 for n >= 7. - _David Callan_, Jul 14 2006
%F A000931 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 A000931 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 A000931 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 A000931 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 A000931 From _Francesco Daddi_, Aug 04 2011: (Start)
%F A000931 a(0) + a(2) + a(4) + a(6) + ... + a(2*n) = a(2*n+3).
%F A000931 a(0) + a(3) + a(6) + a(9) + ... + a(3*n) = a(3*n+2)+1.
%F A000931 a(0) + a(5) + a(10) + a(15) + ... + a(5*n) = a(5*n+1)+1.
%F A000931 a(0) + a(7) + a(14) + a(21) + ... + a(7*n) = (a(7*n) + a(7*n+1) + 1)/2. (End)
%F A000931 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 A000931 a(n) = A182097(n-3) for n > 2. - _Jonathan Sondow_, Mar 14 2014
%F A000931 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 A000931 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 A000931 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 A000931 For the sequence shifted by 6 terms, a(n) = Sum_{k=ceiling(n/3)..ceiling(n/2)} binomial(k+1,3*k-n) [Doslic-Zubac]. - _N. J. A. Sloane_, Apr 23 2017
%F A000931 From _Joseph M. Shunia_, Jan 21 2020: (Start)
%F A000931 a(2n) = 2*a(n-1)*a(n) + a(n)^2 + a(n+1)^2, for n > 8.
%F A000931 a(2n-1) = 2*a(n)*a(n+1) + a(n-1)^2, for n > 8.
%F A000931 a(2n+1) = 2*a(n+1)*a(n+2) + a(n)^2, for n > 7. (End)
%F A000931 0*a(0) + 1*a(1) + 2*a(2) + ... + n*a(n) = n*a(n+5) - a(n+9) + 2. - _Greg Dresden_ and _Zi Ye_, Jul 02 2021
%F A000931 From _Greg Dresden_ and _Zi Ye_, Jul 06 2021: (Start)
%F A000931 2*a(n) = a(n+2) + a(n-5) for n >= 5.
%F A000931 3*a(n) = a(n+4) - a(n-9) for n >= 9.
%F A000931 4*a(n) = a(n+5) - a(n-9) for n >= 9. (End)
%e A000931 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 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 A000931:=-(1+z)/(-1+z^2+z^3); # _Simon Plouffe_ in his 1992 dissertation; gives sequence without five leading terms
%p A000931 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 A000931 CoefficientList[Series[(1-x^2)/(1-x^2-x^3), {x, 0, 50}], x]
%t A000931 a[0]=1; a[1]=a[2]=0; a[n_]:= a[n]= a[n-2] + a[n-3]; Table[a[n], {n, 0, 50}] (* _Robert G. Wilson v_, May 04 2006 *)
%t A000931 LinearRecurrence[{0,1,1}, {1,0,0}, 50] (* _Harvey P. Dale_, Jan 10 2012 *)
%t A000931 Table[RootSum[-1 -# +#^3 &, 5#^n -6#^(n+1) +4#^(n+2) &]/23, {n,0,50}] (* _Eric W. Weisstein_, Nov 09 2017 *)
%o A000931 (Haskell)
%o A000931 a000931 n = a000931_list !! n
%o A000931 a000931_list = 1 : 0 : 0 : zipWith (+) a000931_list (tail a000931_list)
%o A000931 -- _Reinhard Zumkeller_, Feb 10 2011
%o A000931 (PARI) Vec((1-x^2)/(1-x^2-x^3) + O(x^50)) \\ _Charles R Greathouse IV_, Feb 11 2011
%o A000931 (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 A000931 (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
%o A000931 (Sage)
%o A000931 def A000931_list(prec):
%o A000931 P. = PowerSeriesRing(ZZ, prec)
%o A000931 return P( (1-x^2)/(1-x^2-x^3) ).list()
%o A000931 A000931_list(50) # _G. C. Greubel_, Dec 30 2019
%o A000931 (GAP) a:=[1,0,0];; for n in [4..50] do a[n]:=a[n-2]+a[n-3]; od; a; # _G. C. Greubel_, Dec 30 2019
%o A000931 (Python)
%o A000931 def aupton(nn):
%o A000931 alst = [1, 0, 0]
%o A000931 for n in range(3, nn+1): alst.append(alst[n-2]+alst[n-3])
%o A000931 return alst
%o A000931 print(aupton(49)) # _Michael S. Branicky_, Mar 28 2022
%Y A000931 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 A000931 Closely related to A001608.
%Y A000931 Cf. A000073, A005682-A005691, A103372-A103380, A106510, A145462, A146973, A153462.
%Y A000931 Doubling every term gives A291289.
%K A000931 nonn,easy,nice
%O A000931 0,9
%A A000931 _N. J. A. Sloane_
%E A000931 Edited by _Charles R Greathouse IV_, Mar 17 2010
%E A000931 Deleted certain dangerous or potentially dangerous links. - _N. J. A. Sloane_, Jan 30 2021
# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE