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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

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

%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: 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

%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 D. Jarden, Recurring Sequences. Riveon Lematematika, Jerusalem, 1966.

%D Wilbert Osmond, Growing Trees in Padovan Sequence For The Enhancement of L-System Algorithm, http://cys.or.id/docs/icys2014_abstract_wilbert_osmond.pdf, 2014.

%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.), Birkhaeuser, Basel, 1994, pp. 497-512.

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

%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 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, 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>

%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 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://www.emis.de/journals/EM/expmath/volumes/7/7.html">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 D. Gerdemann <a href="http://www.youtube.com/watch?v=H7BkwoYLVSM">Tuba Fantasy (music generated from Padovan numbers)</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>

%H J. B. Gil, M. D. Weiner & C. Zara, <a href="http://math.aa.psu.edu/~juan/papers/padovan.pdf">Complete Padovan Sequences In Finite Fields</a>

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

%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://algo.inria.fr/ecs/ecs?searchType=1&amp;service=Search&amp;searchTerms=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, 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. - _N. J. A. Sloane_, Sep 16 2012

%H W. Lang: <a href="http://www-itp.physik.uni-karlsruhe.de/~wl/EISpub/A000931.text"> Padovan combinatorics, explicit formula, and sequences with various inputs.</a> - _Wolfdieter Lang_, Jun 15 2010

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

%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 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/PadovanSequence.html">Padovan Sequence</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 S. Zlobin, <a href="http://arXiv.org/abs/math/0601151">A note on arithmetic properties of multiple zeta values</a>

%H <a href="/index/Rea#recLCC">Index to sequences with 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)*C(n-k, i)*C(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), C((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)C(n-k, i)C(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), C((n+k)/3,k)}, where C((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

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

%o (Haskell)

%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 */

%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. A103372-A103380, A005682-A005691, A106510, A145462, A146973, A153462, A000073.

%K nonn,easy,nice

%O 0,9

%A _N. J. A. Sloane_

%E Removed attribute "conjectured" from _Simon Plouffe_ g.f. _R. J. Mathar_, Mar 11 2009

%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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified September 19 15:54 EDT 2014. Contains 246977 sequences.