|
%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 (jsondow(AT)alumni.princeton.edu and 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,...). [From Gary W. Adamson, Oct 10 2008]
%C Triangle A145462: right border = A000931 starting with offset 6. Row sums = Padovan sequence starting with offset 7. [From 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,...] [From 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 . [From _Philippe DELEHAM_, Dec 12 2008]
%C Contribution from Gary W. Adamson, Dec 27 2008: (Start)
%C With offset 3: (1, 0, 1, 1, 1, 2, 2,...) convolved with the Tribonacci numbers
%C prefaced with a "1": (1, 1, 1, 2, 4, 7, 13,...) = the Tribonacci numbers, A000073. (Cf. triangle A153462). (End)
%C Contribution from _Toby Gottfried_, Mar 02 2010: 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)
%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)(analogon of the Binet-de Moivre formula for Fibonacci numbers)is also given. Padovan sequences with different inputs are also considered there. [From 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 1 2011.
%C When run backwards gives (-1)^n*A050935(n).
%D J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178; http://www.combinatorics.org/Volume_18/PDF/v18i1p178.pdf.
%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 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.
%D 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.
%D T. M. Green, Recurrent sequences and Pascal's triangle, Math. Mag., 41 (1968), 13-21.
%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 A. Ilic, S. Klavzar and Y. Rho, Parity index of binary words and powers of prime words, http://www.fmf.uni-lj.si/~klavzar/preprints/BalancedFibo-submit.pdf, 2012. - From _N. J. A. Sloane_, Sep 27 2012
%D M. Janjic, Recurrence Relations and Determinants, Arxiv preprint arXiv:1112.2466, 2011
%D M. Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5. - From _N. J. A. Sloane_, Sep 16 2012
%D D. Jarden, Recurring Sequences. Riveon Lematematika, Jerusalem, 1966.
%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 M. Waldschmidt, Lectures on Multiple Zeta Values (IMSC 2011), http://www.math.jussieu.fr/~miw/articles/pdf/MZV2011IMSc.pdf
%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 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="http://www.cs.uwaterloo.ca/journals/JIS/index.html">Integer Sequences Related to Compositions without 2's</a>, J. Integer Seqs., Vol. 6, 2003.
%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 Rachel Hall, <a href="http://www.sju.edu/~rhall/Rhythms/poets.pdf">Math for Poets and Drummers</a>.
%H INRIA Algorithms Project, <a href="http://algo.inria.fr/ecs/ecs?searchType=1&service=Search&searchTerms=393">Encyclopedia of Combinatorial Structures 393</a>
%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> [From _Wolfdieter Lang_, Jun 15 2010]
%H _Simon Plouffe_, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures</a>, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
%H _Simon Plouffe_, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">1031 Generating Functions and Conjectures</a>, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
%H I. Stewart, <a href="http://www.fortunecity.com/emachines/e11/86/padovan.html">Tales of a Neglected Number</a>
%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 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 [From Gary Detlefs, Sep 13 2010]
%F Contribution 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
%e 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; [From 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}] (from _Robert G. Wilson v_, May 04 2006)
%t LinearRecurrence[{0,1,1},{1,0,0},50] (* From 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 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,changed
%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
|
