login
a(n) = C(n,0) + C(n,3) + ... + C(n,3[n/3]).
34

%I #108 Aug 28 2023 07:17:16

%S 1,1,1,2,5,11,22,43,85,170,341,683,1366,2731,5461,10922,21845,43691,

%T 87382,174763,349525,699050,1398101,2796203,5592406,11184811,22369621,

%U 44739242,89478485,178956971,357913942,715827883,1431655765,2863311530

%N a(n) = C(n,0) + C(n,3) + ... + C(n,3[n/3]).

%C First differences of A131708. First differences give A024495. - _Paul Curtz_, Nov 18 2007

%C a(n) = upper left term of X^n, where X = the 4 X 4 matrix [1,0,1,0; 1,1,0,0; 0,1,1,1; 0,0,0,1]. - _Gary W. Adamson_, Mar 01 2008

%C M^n * [1,0,0] = [a(n), A024495(n), A024494(n)], where M = a 3 X 3 matrix [1,1,0; 0,1,1; 1,0,1]. Sum of terms = 2^n. Example: M^5 * [1,0,0] = [11, 11, 10], sum = 2^5 = 32. - _Gary W. Adamson_, Mar 13 2009

%C Let M be any endomorphism on any vector space, such that M^3 = 1 (identity). Then (1+M)^n = a(n) + A024494(n)*M + A024495(n)*M^2. - _Stanislav Sykora_, Jun 10 2012

%C Counts closed walks of length (n) at the vertices of a unidirectional triangle, containing a loop at each vertex. - _David Neil McGrath_, Sep 15 2014

%C {A024493, A131708, A024495} is the difference analog of the hyperbolic functions of order 3, {h_1(x), h_2(x), h_3(x)}. For a definition see the reference "Higher Transcendental Functions" and the Shevelev link. - _Vladimir Shevelev_, Jun 08 2017

%D D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 1, 2nd. ed., Problem 38, p. 70.

%D Higher Transcendental Functions, Bateman Manuscript Project, Vol. 3, ed. A. Erdelyi, 1983 (chapter XVIII).

%H Vincenzo Librandi, <a href="/A024493/b024493.txt">Table of n, a(n) for n = 0..1000</a>

%H P. H. Daus, <a href="http://www.jstor.org/stable/3028604">Note on Sums Involving Binomial Coefficients</a>, National Mathematics Magazine, volume 10, number 5, February 1936, pages 165-166.

%H John B. Dobson, <a href="http://arxiv.org/abs/1610.09361">A matrix variation on Ramus's identity for lacunary sums of binomial coefficients</a>, arXiv preprint arXiv:1610.09361 [math.NT], 2016.

%H Arnold T. Saunders, Jr., <a href="https://search.proquest.com/openview/634d87d0ad57748bf7ab4c0e8d99126e">Random Recursive Tree Evolution Algorithms: Identification and Characterization of Classes of Deletion Rules</a>, Ph. D. thesis, The George Washington University, ProQuest Dissertations Publishing (2020) 27830773.

%H Vladimir Shevelev, <a href="https://arxiv.org/abs/1706.01454">Combinatorial identities generated by difference analogs of hyperbolic and trigonometric functions of order n</a>, arXiv:1706.01454 [math.CO], 2017.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,2).

%F a(n) = (1/3)*(2^n+2*cos( n*Pi/3 )).

%F G.f.: (1-x)^2/((1-2*x)*(1-x+x^2)) = (1-2*x+x^2)/(1-3*x+3*x^2-2*x^3). - _Paul Barry_, Feb 11 2004

%F a(n) = (1/3)*(2^n+b(n)) where b(n) is the 6-periodic sequence {2, 1, -1, -2, -1, 1}. - _Benoit Cloitre_, May 23 2004

%F Binomial transform of 1/(1-x^3). G.f.: (1-x)^2/((1-x)^3-x^3) = x/(1-x-2*x^2)+1/(1+x^3); a(n) = Sum_{k=0..floor(n/3)} binomial(n, 3*k); a(n) = Sum_{k=0..n} binomial(n,k)*(cos(2*Pi*k/3+Pi/3)/3+sin(2*Pi*k/3+Pi/3)/sqrt(3)+1/3); a(n) = A001045(n)+sqrt(3)*cos(Pi*n/3+Pi/6)/3+sin(Pi*n/3+Pi*/6)/3+(-1)^n/3. - _Paul Barry_, Jul 25 2004

%F a(n) = Sum_{k=0..n} binomial(n, 3*(n-k)). - _Paul Barry_, Aug 30 2004

%F G.f.: ((1-x)*(1-x^2)*(1-x^3))/((1-x^6)*(1-2*x)). - _Michael Somos_, Feb 14 2006

%F a(n+1)-2a(n) = -A010892(n). - _Michael Somos_, Feb 14 2006

%F E.g.f.: exp(x)*A(x) where A(x) is the e.g.f. for A079978. - _Geoffrey Critzer_, Dec 27 2011

%F Start with x(0)=1, y(0)=0, z(0)=0 and set x(n+1) = x(n) + z(n), y(n+1) = y(n) + x(n), z(n+1) = z(n) + y(n). Then a(n) = x(n). - _Stanislav Sykora_, Jun 10 2012

%F E.g.f.: (exp(2*z)+2*cos(z*sqrt(3/4))*exp(z/2))/3. - _Peter Luschny_, Jul 10 2012

%F Recurrence: a(0) = 1, a(1) = 1, a(2) = 1, a(n) = 3*a(n-1) - 3*a(n-2) + 2*a(n-3). - _Christopher Hunt Gribble_, Mar 25 2014

%F a(m+k) = a(m)*a(k) + A131708(m)*A024495(k) + A024495(m)*A131708(k). - _Vladimir Shevelev_, Jun 08 2017

%p A024493_list := proc(n) local i; series((exp(2*z)+2*cos(z*sqrt(3/4))*exp(z/2)) /3,z,n+2): seq(i!*coeff(%,z,i),i=0..n) end: A024493_list(33); # _Peter Luschny_, Jul 10 2012

%p seq((3*(-1)^(floor((n+1)/3))+(-1)^n+2^(n+1))/6, n=0..33); # _Peter Luschny_, Jun 14 2017

%t nn = 18; a = Sum[x^(3 i)/(3 i)!, {i, 0, nn}]; b = Exp[x];Range[0, nn]! CoefficientList[Series[a b , {x, 0, nn}], x] (* _Geoffrey Critzer_, Dec 27 2011 *)

%t Differences[LinearRecurrence[{3,-3,2},{0,1,2},40]] (* _Harvey P. Dale_, Nov 27 2013 *)

%o (PARI) a(n)=sum(i=0,n,sum(j=0,n,if(n-i-3*j,0,n!/(i)!/(3*j)!)))

%o (PARI) a(n)=sum(k=0,n\3,binomial(n,3*k)) /* _Michael Somos_, Feb 14 2006 */

%o (PARI) a(n)=if(n<0, 0, ([1,0,1;1,1,0;0,1,1]^n)[1,1]) /* _Michael Somos_, Feb 14 2006 */

%o (Magma) I:=[1,1,1]; [n le 3 select I[n] else 3*Self(n-1)-3*Self(n-2)+2*Self(n-3): n in [1..50]]; // _Vincenzo Librandi_, Jun 12 2017

%Y Row sums of A098172.

%Y Cf. A024494, A094715, A094717, A079978 (inv. binom. transf.).

%K nonn,easy

%O 0,4

%A _Clark Kimberling_