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

 

Logo


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)
199
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, 265, 351, 465, 616, 816, 1081, 1432, 1897, 2513, 3329, 4410, 5842, 7739, 10252, 13581, 17991, 23833, 31572, 41824, 55405, 73396, 97229, 128801, 170625 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,9

COMMENTS

Number of compositions of n into parts congruent to 2 mod 3 (offset -1). - Vladeta Jovovic, Feb 09 2005

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

Referred to as N0102 in R. K. Guy's "Anyone for Twopins". - Rainer Rosenthal, Dec 05 2006

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

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

Triangle A145462: right border = A000931 starting with offset 6. Row sums = Padovan sequence starting with offset 7. - Gary W. Adamson, Oct 10 2008

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

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

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

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

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

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

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

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

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

REFERENCES

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

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

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

D. Jarden, Recurring Sequences. Riveon Lematematika, Jerusalem, 1966.

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.

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

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

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

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

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.

LINKS

T. D. Noe, Table of n, a(n) for n=0..1000

Barry Balof, Restricted tilings and bijections, J. Integer Seq. 15 (2012), no. 2, Article 12.2.3, 17 pp.

J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178.

O. Bouillot, The Algebra of Multitangent Functions, 2013

J. S. Brauchart, P. D. Dragnev, E. B. Saff, An Electrostatics Problem on the Sphere Arising from a Nearby Point Charge, 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

F. Brown, On the decomposition of motivic multiple zeta values

P. Chinn and S. Heubach, Integer Sequences Related to Compositions without 2's, J. Integer Seqs., Vol. 6, 2003.

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.

R. Euler, P. Oleksik, Z. Skupien, Counting Maximal Distance-Independent Sets in Grid Graphs, Discussiones Mathematicae Graph Theory. Volume 33, Issue 3, Pages 531-557, ISSN (Print) 2083-5892, DOI: 10.7151/dmgt.1707, July 2013.

P. Flajolet and B. Salvy, Euler Sums and Contour Integral Representations, Experimental Mathematics Vol. 7 issue 1 (1998)

D. Gerdemann Sums of Padovan numbers equal to sums of powers of plastic number (YouTube video)

D. Gerdemann Tuba Fantasy (music generated from Padovan numbers)

J. B. Gil, M. D. Weiner & C. Zara, Complete Padovan sequences in finite fields

J. B. Gil, M. D. Weiner & C. Zara, Complete Padovan Sequences In Finite Fields

Juan B. Gil, Michael D. Weiner and Catalin Zara, Complete Padovan sequences in finite fields, The Fibonacci Quarterly, vol. 45 (Feb 2007 issue), pp. 64 - 75.

N. Gogin and A. Mylläri, Padovan-like sequences and Bell polynomials, Proceedings of Applications of Computer Algebra ACA, 2013.

T. M. Green, Recurrent sequences and Pascal's triangle, Math. Mag., 41 (1968), 13-21.

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.

Rachel Hall, Math for Poets and Drummers.

A. Ilic, S. Klavzar and Y. Rho, Parity index of binary words and powers of prime words, 2012. - N. J. A. Sloane, Sep 27 2012

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 393

M. Janjic, Recurrence Relations and Determinants, arXiv preprint arXiv:1112.2466, 2011

M. Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5. - N. J. A. Sloane, Sep 16 2012

W. Lang: Padovan combinatorics, explicit formula, and sequences with various inputs. - Wolfdieter Lang, Jun 15 2010

R. J. Mathar, Paving rectangular regions with rectangular tiles,...., arXiv:1311.6135 [math.CO], Table 49.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

I. Stewart, Tales of a Neglected Number

M. Waldschmidt, Lectures on Multiple Zeta Values (IMSC 2011).

Eric Weisstein's World of Mathematics, Padovan Sequence

E. Wilson, The Scales of Mt. Meru

I. Wloch, U. Bednarz, D. Bród, A Wloch and M. Wolowiec-Musial, On a new type of distance Fibonacci numbers, Discrete Applied Math., Volume 161, Issues 16-17, November 2013, Pages 2695-2701.

S. Zlobin, A note on arithmetic properties of multiple zeta values

Index to sequences with linear recurrences with constant coefficients, signature (0,1,1).

FORMULA

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

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

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

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

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

G.f.: 1/(1-x^3-x^5-x^7-x^9-....). - Jon Perry, Jul 04 2004

a(n+4)=sum{k=0..floor((n-1)/2), binomial(floor((n+k-2)/3), k)}. - Paul Barry, Jul 06 2004

a(n)=sum{k=0..floor(n/2), binomial(k, n-2k)}. - Paul Barry, Sep 17 2004

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

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

a(n+3)=sum{k=0..floor(n/2), C((n-k)/2, k)(1+(-1)^(n-k))/2}. - Paul Barry, Sep 09 2005

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

a(n) = A023434(n-7)+1 for n>=7. - David Callan, Jul 14 2006

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

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

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

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

From Francesco Daddi, Aug 04 2011:  (Start)

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

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

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

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

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

a(n) = A182097(n-3) for n > 2. - Jonathan Sondow, Mar 14 2014

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

EXAMPLE

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

MAPLE

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

A000931:=-(1+z)/(-1+z^2+z^3); # Simon Plouffe in his 1992 dissertation. Gives sequence without five leading terms.

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

MATHEMATICA

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

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

LinearRecurrence[{0, 1, 1}, {1, 0, 0}, 50] (* Harvey P. Dale, Jan 10 2012 *)

PROG

(Haskell)

a000931 n = a000931_list !! n

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

-- Reinhard Zumkeller, Feb 10 2011

(PARI) Vec((1-x^2)/(1-x^2-x^3)+O(x^99)) \\ Charles R Greathouse IV, Feb 11 2011

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

CROSSREFS

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.

Closely related to A001608.

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

Sequence in context: A018124 A124745 A133034 * A078027 A134816 A228361

Adjacent sequences:  A000928 A000929 A000930 * A000932 A000933 A000934

KEYWORD

nonn,easy,nice,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

Removed attribute "conjectured" from Simon Plouffe g.f. R. J. Mathar, Mar 11 2009

Edited by Charles R Greathouse IV, Mar 17 2010

STATUS

approved

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 October 24 03:37 EDT 2014. Contains 248491 sequences.