login
A024493
a(n) = C(n,0) + C(n,3) + ... + C(n,3[n/3]).
34
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,4
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
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.
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
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 *)
PROG
(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 */
(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
CROSSREFS
Row sums of A098172.
Cf. A024494, A094715, A094717, A079978 (inv. binom. transf.).
Sequence in context: A091357 A309950 A129715 * A130781 A352045 A351970
KEYWORD
nonn,easy
STATUS
approved