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

1, 1, 1, 2, 5, 11, 22, 43, 85, 170, 341, 683, 1366, 2731, 5461, 10922, 21845, 43691, 87382, 174763, 349525, 699050, 1398101, 2796203, 5592406, 11184811, 22369621, 44739242, 89478485, 178956971, 357913942, 715827883, 1431655765, 2863311530

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• easy

Comments

First differences of A131708. First differences give A024495. - Paul Curtz, Nov 18 2007

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

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

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

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

{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

References

• D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 1, 2nd. ed., Problem 38, p. 70.
• Higher Transcendental Functions, Bateman Manuscript Project, Vol. 3, ed. A. Erdelyi, 1983 (chapter XVIII).

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• P. H. Daus, Note on Sums Involving Binomial Coefficients, National Mathematics Magazine, volume 10, number 5, February 1936, pages 165-166.
• John B. Dobson, A matrix variation on Ramus's identity for lacunary sums of binomial coefficients, arXiv preprint arXiv:1610.09361 [math.NT], 2016.
• Arnold T. Saunders, Jr., Random Recursive Tree Evolution Algorithms: Identification and Characterization of Classes of Deletion Rules, Ph. D. thesis, The George Washington University, ProQuest Dissertations Publishing (2020) 27830773.
• Vladimir Shevelev, Combinatorial identities generated by difference analogs of hyperbolic and trigonometric functions of order n, arXiv:1706.01454 [math.CO], 2017.
• Index entries for linear recurrences with constant coefficients, signature (3,-3,2).

Crossrefs

Row sums of A098172.

Cf. A024494, A094715, A094717, A079978 (inverse binomial transform).

Programs

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

Maple

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
seq((3*(-1)^(floor((n+1)/3))+(-1)^n+2^(n+1))/6, n=0..33); # Peter Luschny, Jun 14 2017

Mathematica

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 *)
Differences[LinearRecurrence[{3,-3,2},{0,1,2},40]] (* Harvey P. Dale, Nov 27 2013 *)

PARI

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

PARI

a(n)=sum(k=0,n\3,binomial(n,3*k)) /* Michael Somos, Feb 14 2006 */

PARI

a(n)=if(n<0, 0, ([1,0,1;1,1,0;0,1,1]^n)[1,1]) /* Michael Somos, Feb 14 2006 */

Formula

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

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

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

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

a(n) = Sum_{k=0..n} binomial(n, 3*(n-k)). - Paul Barry, Aug 30 2004

G.f.: ((1-x)*(1-x^2)*(1-x^3))/((1-x^6)*(1-2*x)). - Michael Somos, Feb 14 2006

a(n+1)-2a(n) = -A010892(n). - Michael Somos, Feb 14 2006

E.g.f.: exp(x)*A(x) where A(x) is the e.g.f. for A079978. - Geoffrey Critzer, Dec 27 2011

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

E.g.f.: (exp(2*z)+2*cos(z*sqrt(3/4))*exp(z/2))/3. - Peter Luschny, Jul 10 2012

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

a(m+k) = a(m)*a(k) + A131708(m)*A024495(k) + A024495(m)*A131708(k). - Vladimir Shevelev, Jun 08 2017