cp's OEIS Frontend

A004006 a(n) = C(n,1) + C(n,2) + C(n,3), or n*(n^2 + 5)/6.

%I A004006 #176 Jun 19 2025 00:14:16
%S A004006 0,1,3,7,14,25,41,63,92,129,175,231,298,377,469,575,696,833,987,1159,
%T A004006 1350,1561,1793,2047,2324,2625,2951,3303,3682,4089,4525,4991,5488,
%U A004006 6017,6579,7175,7806,8473,9177,9919,10700,11521,12383,13287,14234,15225
%N A004006 a(n) = C(n,1) + C(n,2) + C(n,3), or n*(n^2 + 5)/6.
%C A004006 3-dimensional analog of centered polygonal numbers.
%C A004006 The Burnside group B(3,n) has order 3^a(n).
%C A004006 Answer to the question: if you have a tall building and 3 plates and you need to find the highest story, a plate thrown from which does not break, what is the number of stories you can handle given n tries? - _Leonid Broukhis_, Oct 24 2000
%C A004006 Equals row sums of triangle A144329 starting with "1". - _Gary W. Adamson_, Sep 18 2008
%C A004006 Let A be the Hessenberg matrix of order n, defined by: A[1,j]=A[i,i]:=1, A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=4, a(n-1)=-coeff(charpoly(A,x),x^(n-3)). - _Milan Janjic_, Jan 24 2010
%C A004006 From _J. M. Bergot_, Aug 03 2011: (Start)
%C A004006 If one formed the 3 X 3 square
%C A004006   |  n  |  n+1 | n+2 |
%C A004006   | n+3 |  n+4 | n+5 |
%C A004006   | n+6 |  n+7 | n+8 |
%C A004006   and found the sum of the horizontal products n*(n + 1)*(n + 2) + (n + 3)*(n + 4)*(n + 5) + (n + 6)*(n + 7)*(n + 8) and added the sum of the vertical products n*(n + 3)*(n + 6) + (n + 1)*(n + 4)*(n + 7) + (n + 2)*(n + 5)(n + 8) one gets 6*n^3 + 72*n^2 + 318*n + 504. This will give 36 times the values of all the terms in this sequence. (End)
%C A004006 a(n) is divisible by n for n congruent to {1,5} mod 6. (see A007310). - _Gary Detlefs_, Dec 08 2011
%C A004006 From _Beimar Naranjo_, Feb 22 2024: (Start)
%C A004006 Number of compositions with at most three parts and sum at most n.
%C A004006 Also the number of compositions with at most one part distinct from 1 and with a sum at most n. (End)
%C A004006 a(n) is the number of strings of length n defined on {0, 1, 2, 3} that contain one 1 and any number of 0's, or two 2's and any number of 0's, or three 3's and any number of 0's. For example, a(6) = 41 since the strings are the 20 permutations of 333000, the 15 permutations of 220000 and the 6 permutations of 100000. - _Enrique Navarrete_, Jun 18 2025
%D A004006 W. Magnus, A. Karrass and D. Solitar, Combinatorial Group Theory, Wiley, 1966, see p. 380.
%H A004006 Vincenzo Librandi, <a href="/A004006/b004006.txt">Table of n, a(n) for n = 0..5000</a>
%H A004006 Michael Boardman, <a href="http://www.jstor.org/stable/3219201">The Egg-Drop Numbers</a>, Mathematics Magazine, 77 (2004), 368-372. [From Parthasarathy Nambi, Sep 30 2009]
%H A004006 F. Javier de Vega, <a href="https://arxiv.org/abs/2003.13378">An extension of Furstenberg's theorem of the infinitude of primes</a>, arXiv:2003.13378 [math.NT], 2020.
%H A004006 Oboifeng Dira, <a href="http://www.seams-bull-math.ynu.edu.cn/downloadfile.jsp?filemenu=_201706&amp;filename=07_41(6).pdf">A Note on Composition and Recursion</a>, Southeast Asian Bulletin of Mathematics, 2017, Vol. 41 Issue 6, pp. 849-853.
%H A004006 N. Heninger, E. M. Rains and N. J. A. Sloane, <a href="https://arxiv.org/abs/math/0509316">On the Integrality of n-th Roots of Generating Functions</a>, arXiv:math/0509316 [math.NT], 2005-2006.
%H A004006 N. Heninger, E. M. Rains and N. J. A. Sloane, <a href="https://doi.org/10.1016/j.jcta.2006.03.018">On the Integrality of n-th Roots of Generating Functions</a>, J. Combinatorial Theory, Series A, 113 (2006), 1732-1745.
%H A004006 Milan Janjić, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Janjic/janjic33.html">Hessenberg Matrices and Integer Sequences</a>, J. Int. Seq. 13 (2010) # 10.7.8.
%H A004006 T. P. Martin, <a href="http://dx.doi.org/10.1016/0370-1573(95)00083-6">Shells of atoms</a>, Phys. Reports, 273 (1996), 199-241, eq. (11).
%H A004006 Laurent Saloff-Coste, <a href="http://www.math.cornell.edu/~lsc/chap5.pdf">Random walks on finite groups</a>, in Probability on discrete structures, 263-346, Encyclopaedia Math. Sci., 110, Springer, 2004.
%H A004006 Bridget Eileen Tenner, <a href="https://doi.org/10.1007/s10801-017-0752-8">Reduced word manipulation: patterns and enumeration</a>, J. Algebr. Comb. 46, No. 1, 189-217 (2017), w in S_n(231) l(w)=3.
%H A004006 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-6,4,-1).
%F A004006 G.f.: x*(1-x+x^2)/(1-x)^4.
%F A004006 E.g.f.: x*(1 + x/2 + x^2/6) * exp(x).
%F A004006 a(-n) = -a(n).
%F A004006 a(n) = binomial(n+2,n-1) - binomial(n,n-2). - _Zerinvary Lajos_, May 11 2006
%F A004006 Euler transform of length 6 sequence [3, 1, 1, 0, 0, -1]. - _Michael Somos_, May 04 2007
%F A004006 Starting (1, 3, 7, 14, ...) = binomial transform of [1, 2, 2, 1, 0, 0, 0, ...]. - _Gary W. Adamson_, Apr 24 2008
%F A004006 a(0)=0, a(1)=1, a(2)=3, a(3)=7, a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4). - _Harvey P. Dale_, Aug 21 2011
%F A004006 a(n+1) = A000292(n) + n + 1. - _Reinhard Zumkeller_, Mar 31 2012
%F A004006 a(n) = 2*a(n-1) + (n-1) - a(n-2) with a(0) = 0, a(1) = 1. - _Richard R. Forberg_, Jan 23 2014
%F A004006 a(n) = Sum_{i=1..n} binomial(n-2i,2). - _Wesley Ivan Hurt_, Nov 18 2017
%F A004006 a(n) = n + Sum_{k=0..n} k*(n-k). - _Gionata Neri_, May 19 2018
%F A004006 a(n) = Sum_{k=0..n-1} A000124(k). - _Torlach Rush_, Aug 05 2018
%F A004006 G.f.: ((1 - x^5)/(1 - x)^5 - 1)/5. - _Michael Somos_, Dec 29 2019
%F A004006 G.f.: g(f(x)), where g is g.f. of A001477 and f is g.f. of A128834. - _Oboifeng Dira_, Jun 21 2020
%F A004006 Sum_{n>0} 1/a(n) = 3*(2*gamma + polygamma(0, 1-i*sqrt(5)) + polygamma(0, 1+i*sqrt(5)))/5 = 1.6787729555834452106286261834348972248... where i denotes the imaginary unit. - _Stefano Spezia_, Aug 31 2023
%e A004006 G.f. = x + 3*x^2 + 7*x^3 + 14*x^4 + 25*x^5 + 41*x^6 + 63*x^7 + 92*x^8 + ... - _Michael Somos_, Dec 29 2019
%p A004006 A004006 := proc(n) n*(n^2+5)/6 ;end proc:
%p A004006 seq(A004006(n),n=0..10) ; # _R. J. Mathar_, Jun 05 2011
%t A004006 Table[Total[Table[Binomial[n,i], {i,3}]], {n,0,50}] (* or *) LinearRecurrence[{4,-6,4,-1}, {0,1,3,7}, 50] (* _Harvey P. Dale_, Aug 21 2011 *)
%o A004006 (PARI) {a(n) = n*(n^2 + 5)/6}; /* _Michael Somos_, May 04 2007 */
%o A004006 (Magma) [n*(n^2+5)/6: n in [0..50]]; // _Vincenzo Librandi_, May 15 2011
%o A004006 (Haskell)
%o A004006 a004006 n = a000292 n + n + 1  -- _Reinhard Zumkeller_, Mar 31 2012
%o A004006 (Maxima) A004006(n):=n*(n^2+5)/6$ makelist(A004006(n),n,0,30); /* _Martin Ettl_, Jan 08 2013 */
%o A004006 (Sage) [n*(n^2+5)/6 for n in (0..50)] # _G. C. Greubel_, Aug 27 2019
%o A004006 (GAP) List([0..50], n-> n*(n^2+5)/6); # _G. C. Greubel_, Aug 27 2019
%Y A004006 Cf. A051576, A055795, A006552. Differences give A000217 + 1 or A000124.
%Y A004006 1/12*t*(n^3-n)+n for t = 2, 4, 6, ... gives A004006, A006527, A006003, A005900, A004068, A000578, A004126, A000447, A004188, A004466, A004467, A007588, A062025, A063521, A063522, A063523.
%Y A004006 Cf. A000292, A001477, A007310, A128834, A144329, A228074.
%K A004006 nonn,nice,easy
%O A004006 0,3
%A A004006 Albert D. Rich (Albert_Rich(AT)msn.com)