A024495 -id:A024495 - cp's OEIS frontend

A079309 a(n) = C(1,1) + C(3,2) + C(5,3) + ... + C(2*n-1,n).

1, 4, 14, 49, 175, 637, 2353, 8788, 33098, 125476, 478192, 1830270, 7030570, 27088870, 104647630, 405187825, 1571990935, 6109558585, 23782190485, 92705454895, 361834392115, 1413883873975, 5530599237775, 21654401079325, 84859704298201, 332818970772253

Offset: 1

Miklos Kristof, Feb 10 2003

a(n) is the sum of pyramid weights of all Dyck paths of length 2n (for pyramid weight see Denise and Simion). Equivalently, a(n) is the sum of the total lengths of end branches of an ordered tree, summation being over all ordered trees with n edges. For example, the five ordered trees with 3 edges have total lengths of endbranches 3,2,3,3 and 3. - Emeric Deutsch, May 30 2003
a(n) is the number of Motzkin paths of length 2n with exactly one level segment. (A level segment is a maximal sequence of contiguous flatsteps.) Example: for n=2, the paths counted are FFFF, FFUD, UDFF, UFFD. The formula for a(n) below counts these paths by length of the level segment. - David Callan, Jul 15 2004
The inverse Catalan transform yields A024495, shifted once left. - R. J. Mathar, Jul 07 2009
From Paul Barry, Mar 29 2010: (Start)
Hankel transform is A138341.
The aerated sequence 0, 0, 1, 0, 4, 0, 14, 0, 49, ... has e.g.f. int(cosh(x-t)*Bessel_I(1,2t), t = 0..x). (End)
a(n) is the number of terms of A031443 not exceeding 4^n. - Vladimir Shevelev, Oct 01 2010
Also the number of nonempty subsets of {1..2n} with median n, bisection of A361801. The version containing n is A001700 (bisected). Replacing 2n with 2n+1 and n with n+1 gives A006134. For mean instead of median we have A212352. - Gus Wiseman, Apr 16 2023

			a(4) = C(1,1) + C(3,2) + C(5,3) + C(7,4) = 1 + 3 + 10 + 35 = 49.
G.f. = x + 4*x^2 + 14*x^3 + 49*x^4 + 175*x^5 + 637*x^6 + 2353*x^7 + ...
From _Gus Wiseman_, Apr 16 2023: (Start)
The a(1) = 1 through a(3) = 14 subsets of {1..2n} with median n:
  {1}  {2}      {3}
       {1,3}    {1,5}
       {1,2,3}  {2,4}
       {1,2,4}  {1,3,4}
                {1,3,5}
                {1,3,6}
                {2,3,4}
                {2,3,5}
                {2,3,6}
                {1,2,4,5}
                {1,2,4,6}
                {1,2,3,4,5}
                {1,2,3,4,6}
                {1,2,3,5,6}
(End)

Vincenzo Librandi and Robert Israel, Table of n, a(n) for n = 1..1500 (terms 1..200 from Vincenzo Librandi).
A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155-176.
Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
R. Witula, Ramanujan type trigonometric formulas, Demonstratio Mathematica, Vol. XLV, No. 4 (2012), 789-796. - From _N. J. A. Sloane_, Jan 01 2013

Cf. A001700, A024495, A066796, A138341.
Equals A024718(n) - 1.
This is the even (or odd) bisection of A361801.
A007318 counts subsets by length, A327481 by mean, A013580 by median.
A359893 and A359901 count partitions by median.
Cf. A000975, A057552, A231147, A361654, A361864, A362046.

a := n -> add(binomial(2*j, j)/2, j=1..n): seq(a(n), n=1..24); # Zerinvary Lajos, Oct 25 2006
a := n -> add(abs(binomial(-j, -2*j)), j=1..n): seq(a(n), n=1..24); # Zerinvary Lajos, Oct 03 2007
f:= gfun:-rectoproc({n*a(n) +(-5*n+2)*a(n-1) +2*(2*n-1)*a(n-2)=0,a(1)=1,a(2)=4},a(n),remember):
map(f, [$1..100]); # Robert Israel, Jun 24 2015

Rest[CoefficientList[Series[(1/Sqrt[1-4*x]-1)/(1-x)/2, {x, 0, 20}], x]] (* Vaclav Kotesovec, Feb 13 2014 *)
Accumulate[Table[Binomial[2n-1,n],{n,30}]] (* Harvey P. Dale, Jan 06 2021 *)

{a(n) = sum(k=1, n, binomial(2*k - 1, k))}; /* Michael Somos, Feb 14 2006 */

my(x='x+O('x^40)); Vec((1/sqrt(1-4*x)-1)/(1-x)/2) \\ Altug Alkan, Dec 24 2015

a(n) = (1/2)*(C(2, 1) + C(4, 2) + C(6, 3) + ... + C(2*n, n)) = A066796(n)/2. - Vladeta Jovovic, Feb 12 2003
G.f.: (1/sqrt(1 - 4*x) - 1)/(1 - x)/2. - Vladeta Jovovic, Feb 12 2003
Given g.f. A(x), then x * A(x - x^2) is g.f. of A024495. - Michael Somos, Feb 14 2006
a(n) = A066796(n)/2. - Zerinvary Lajos, Oct 25 2006
a(n) = Sum_{0 <= i <= j <= n} binomial(i+j, i). - Benoit Cloitre, Nov 25 2006
D-finite with recurrence n*a(n) + (-5*n+2)*a(n-1) + 2*(2*n-1)*a(n-2) = 0. - R. J. Mathar, Nov 30 2012
a(n) ~ 2^(2*n+1) / (3*sqrt(Pi*n)). - Vaclav Kotesovec, Feb 13 2014
a(n) = Sum_{k=0..n-1} A001700(k). - Doug Bell, Jun 23 2015
a(n) = -binomial(2*n+1, n)*hypergeom([1, n+3/2], [n+2], 4) - (i/sqrt(3) + 1)/2. - Peter Luschny, May 18 2018
From Gus Wiseman, Apr 18 2023: (Start)
a(n) = A024718(n) - 1.
a(n) = A231147(2n+1,n).
a(n) = A361801(2n) = A361801(2n+1). (End)
a(n) = Sum_{k=0..floor(n/2)} (-1)^k*binomial(2*n+2-k, n-2*k). - Michael Weselcouch, Jun 17 2025
a(n) = binomial(2*(1+n), n)*hypergeom([1, (1-n)/2, -n/2], [-2*(1+n), 3+n], 4). - Stefano Spezia, Jun 18 2025

More terms from Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 11 2003

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

Original entry on oeis.org

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

Clark Kimberling

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

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).

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).

Row sums of A098172.

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

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

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

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 *)

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

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

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

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

A038503 Sum of every 4th entry of row n in Pascal's triangle, starting at "n choose 0".

Original entry on oeis.org

1, 1, 1, 1, 2, 6, 16, 36, 72, 136, 256, 496, 992, 2016, 4096, 8256, 16512, 32896, 65536, 130816, 261632, 523776, 1048576, 2098176, 4196352, 8390656, 16777216, 33550336, 67100672, 134209536, 268435456, 536887296, 1073774592, 2147516416, 4294967296, 8589869056, 17179738112

Offset: 0

Frank Ruskey

Number of strings over Z_2 of length n with trace 0 and subtrace 0.
Same as number of strings over GF(2) of length n with trace 0 and subtrace 0.
M^n = [1,0,0,0] = [a(n), A000749(n), A038505(n), A038504(n)]; where M = the 4 X 4 matrix [1,1,0,0; 0,1,1,0; 0,0,1,1; 1,0,0,1]. Sum of the 4 terms = 2^n. Example: M^6 = [16, 20, 16, 12], sum of terms = 64 = 2^6. - Gary W. Adamson, Mar 13 2009
a(n) is the number of generalized compositions of n when there are i^2/2 - 5i/2 + 3 different types of i, (i=1,2,...). - Milan Janjic, Sep 24 2010
{A038503, A038504, A038505, A000749} is the difference analog of the hyperbolic functions {h_1(x), h_2(x), h_3(x), h_4(x)} of order 4. For the definitions of {h_i(x)} and the difference analog {H_i (n)} see [Erdelyi] and the Shevelev link respectively. - Vladimir Shevelev, Aug 01 2017

			a(3;0,0)=1 since the one binary string of trace 0, subtrace 0 and length 3 is { 000 }.

A. Erdelyi, Higher Transcendental Functions, McGraw-Hill, 1955, Vol. 3, Chapter XVIII.
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 1, 2nd ed., Problem 38, p. 70, gives an explicit formula for the sum.

Seiichi Manyama, Table of n, a(n) for n = 0..3000
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5, pp. 1-24.
John B. Dobson, A matrix variation on Ramus's identity for lacunary sums of binomial coefficients, arXiv preprint arXiv:1610.09361 [math.NT], 2016.
Frank Ruskey, Strings over Z_2 with given trace and subtrace
Frank Ruskey, Strings over GF(2) with given trace and subtrace
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 (4,-6,4).

Cf. A024493, A024494, A024495, A038505, A038504, A000749.

Row sums of A098173.

A038503_list := proc(n) local i; series(exp(z)*(cosh(z)+cos(z))/2,z,n+2):
seq(i!*coeff(%,z,i),i=0..n) end: A038503_list(32); # Peter Luschny, Jul 10 2012
a := n -> hypergeom([1/4 - n/4, 1/2 - n/4, 3/4 - n/4, -n/4], [1/4, 1/2, 3/4], 1):
seq(simplify(a(n)), n = 0..36); # Peter Luschny, Mar 18 2023

nn = 18; a = Sum[x^(4 i)/(4 i)!, {i, 0, nn}]; b = Exp[x];Range[0, nn]! CoefficientList[Series[a b, {x, 0, nn}], x]  (* Geoffrey Critzer, Dec 27 2011 *)
Join[{1},LinearRecurrence[{4,-6,4},{1,1,1},40]] (* Harvey P. Dale, Dec 02 2014 *)

a(n) = sum(k=0, n\4, binomial(n, 4*k)); \\ Michel Marcus, Mar 13 2019

From Paul Barry, Mar 18 2004: (Start)
G.f.: (1-x)^3/((1-x)^4-x^4);
a(n) = Sum_{k=0..floor(n/4)} binomial(n, 4k); a(n) = 2^(n-1) + 2^((n-2)/2)(cos(Pi*n/4) - sin(Pi*n/4)). (End)
Binomial transform of 1/(1-x^4). a(n) = 4a(n-1) - 6a(n-2) + 4a(n-3); a(n) = Sum_{k=0..n} binomial(n, k)(sin(Pi*(k+1)/2)/2 + (1+(-1)^k)/4); a(n) = Sum_{k=0..floor(n/4)} binomial(n, 4k). - Paul Barry, Jul 25 2004
a(n) = Sum_{k=0..n} binomial(n, 4(n-k)). - Paul Barry, Aug 30 2004
a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2k)(1+(-1)^k)/2. - Paul Barry, Nov 29 2004
a(n; t, s) = a(n-1; t, s) + a(n-1; t+1, s+t+1) where t is the trace and s is the subtrace.
E.g.f.: exp(z)*(cosh(z) + cos(z))/2. - Peter Luschny, Jul 10 2012
From Vladimir Shevelev, Aug 01 2017: (Start)
For n >= 1, {H_i(n)} are linearly dependent sequences: a(n) = H_1(n) = H_2(n) - H_3(n) + H_4(n);
a(n+m) = a(n)*a(m) + H_4(n)*H_2(m) + H_3(n)*H_3(m) + H_2(n)*H_4(m), where H_2 = A038504, H_3 = A038505, H_4 = A000749.
For proofs, see Shevelev's link, Theorems 2, 3. (End)
a(n) = hypergeom([1/4 - n/4, 1/2 - n/4, 3/4 - n/4, -n/4], [1/4, 1/2, 3/4], 1). - Peter Luschny, Mar 18 2023

A131534 Period 3: repeat [1, 2, 1].

Original entry on oeis.org

1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1

Offset: 0

Paul Curtz, Aug 26 2007

Partial sums of A106510. Inverse binomial transform of A024495 (without leading zeros). - Philippe Deléham, Nov 26 2008
a(n) = A130196(n) - A022003(n) = A080425(n) - A130196(n)+2 = A153727(n)/A130196(n). - Reinhard Zumkeller, Nov 12 2009
Continued fraction expansion of A177346, (1+sqrt(10))/3. - Klaus Brockhaus, May 07 2010
From Daniel Forgues, May 04 2016: (Start)
a(n) = GCD of terms of the sequence S_n = {F_i+F_{i+1}+F_{i+2}+...+F_{i+2n}, i >= 0}, where F_i denotes a Fibonacci number. See A210209.
a(n) = GCD of terms of the sequence S_n = {L_i+L_{i+1}+L_{i+2}+...+L_{i+2n}, i >= 0}, where L_i denotes a Lucas number. See A229339. (End)

Index entries for linear recurrences with constant coefficients, signature (0,0,1).

Cf. A167808. - Reinhard Zumkeller, Nov 12 2009

Cf. A000045, A022003, A024495, A080425, A101825, A106510, A130196, A153727, A177346, A210209, A229339.

[(-n mod 3)^(n mod 3) : n in [0..100]]; // Wesley Ivan Hurt, Aug 29 2014

A131534:=n->(-n mod 3)^(n mod 3): seq(A131534(n), n=0..100); # Wesley Ivan Hurt, Aug 29 2014

PadRight[{},120,{1,2,1}] (* Harvey P. Dale, Aug 06 2013 *)

a(n)=1+(n%3==1) \\ Jaume Oliver Lafont, Mar 20 2009

G.f.: (x+1)^2/((1-x)*(x^2+x+1)). - R. J. Mathar, Nov 14 2007
a(n) = 4/3 + (2/3)*cos(2*Pi*(n+2)/3). - Jaume Oliver Lafont, May 09 2008
a(n) = A101825(n+1). - R. J. Mathar, Jun 13 2008
a(n) = gcd(F(n)^2+F(n+1)^2, F(n)+F(n+1)). - Gary Detlefs, Dec 29 2010
a(n) = 2 - ((n+2)^2 mod 3). - Gary Detlefs, Oct 13 2011
a(n) = ceiling(n*4/3) - ceiling((n-1)*4/3). - Tom Edgar, Jul 22 2014
a(n) = 2 - abs(3*floor(n/3)+1-n). - Mikael Aaltonen, Jan 02 2015
a(n) = 1+[3|(2n+1)], using Iverson bracket. - Daniel Forgues, May 04 2016
a(n) = a(n-3) for n>2. - Wesley Ivan Hurt, Jul 05 2016
E.g.f.: (4*exp(x) - exp(-x/2)*(cos(sqrt(3)*x/2) - sqrt(3)*sin(sqrt(3)*x/2)))/3. - Stefano Spezia, Aug 04 2025

A131708 A024494 prefixed by a 0.

Original entry on oeis.org

0, 1, 2, 3, 5, 10, 21, 43, 86, 171, 341, 682, 1365, 2731, 5462, 10923, 21845, 43690, 87381, 174763, 349526, 699051, 1398101, 2796202, 5592405, 11184811, 22369622, 44739243, 89478485, 178956970, 357913941, 715827883, 1431655766, 2863311531, 5726623061, 11453246122

Offset: 0

Paul Curtz, Sep 14 2007, Mar 01 2008

Binomial transform of 0, 1, 0. Also A024495 = first differences.
Recurrence: a(n+1) - 2*a(n) = 1, 0, -1, -1, 0, 1, 1.
{A024493, A131708, A024495} is the difference analog of the hyperbolic functions {h_1(x), h_2(x), h_3(x)} of order 3. For the definitions of {h_i(x)} and the difference analog {H_i(n)} see [Erdelyi] and the Shevelev link respectively. - Vladimir Shevelev, Aug 01 2017

A. Erdelyi, Higher Transcendental Functions, McGraw-Hill, 1955, Vol. 3, Chapter XVIII.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Antoine-Augustin Cournot, Solution d'un problème d'analyse combinatoire, Bulletin des Sciences Mathématiques, Physiques et Chimiques, item 34, volume 11, 1829, pages 93-97. Also at Google Books. Page 97 case p=3 formula y^(1) = a(n).
Christian Ramus, Solution générale d'un problème d'analyse combinatoire, Journal für die Reine und Angewandte Mathematik (Crelle's journal), volume 11, 1834, pages 353-355. Page 353 case p=3 formula y^(1) = a(n).
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).

Cf. A024493, A024494, A024495, A111927, A113405, A135350, A137221.

[n le 3 select n-1 else 3*Self(n-1) -3*Self(n-2) +2*Self(n-3): n in [1..40]]; // G. C. Greubel, Jan 23 2023

LinearRecurrence[{3,-3,2}, {0,1,2}, 40] (* Harvey P. Dale, Nov 27 2013 *)

v=vector(99,i,i);for(i=4,#v,v[i]=3*v[i-1]-3*v[i-2]+2*v[i-3]);v \\ Charles R Greathouse IV, Jun 01 2011

def A131708(n): return (1/3)*(2^n -chebyshev_U(n,1/2) +2*chebyshev_U(n-1,1/2))
[A131708(n) for n in range(41)] # G. C. Greubel, Jan 23 2023

G.f.: x*(1-x)/((1-2*x)*(1-x+x^2)). - R. J. Mathar, Nov 14 2007
Recurrences:
a(n) = k*a(n-1) + (6-3*k)*a(n-2) + (3*k-7)*a(n-3) + (6-2*k)*a(n-4).
k = 0: a(n) = 6*a(n-2) - 7*a(n-3) + 6*a(n-4).
k = 1: a(n) = a(n-1) + 3*a(n-2) - 4*a(n-3) + 4*a(n-4).
k = 2: a(n) = 2*a(n-1) - a(n-3) + 2*a(n-4), cf. A113405, A135350.
k = 3: a(n) = 3*a(n-1) - 3*a(n-2) + 2*a(n-3), this sequence.
k = 4: a(n) = 4*a(n-1) - 6*a(n-2) + 5*a(n-3) - 2*a(n-4), cf. A111927.
k = 5: a(n) = 5*a(n-1) - 9*a(n-2) + 8*a(n-3) - 4*a(n-4), cf. A137221.
The sum of coefficients = 5 - k. Of the family k=3 gives the best recurrence.
a(n+m) = a(n)*A024493(m) + A024493(n)*a(m) + A024495(n)*A024495(m). - Vladimir Shevelev, Aug 01 2017
From Kevin Ryde, Sep 24 2020: (Start)
a(n) = (1/3)*2^n - (1/3)*cos((1/3)*Pi*n) + (1/sqrt(3))*sin((1/3)*Pi*n). [Cournot]
a(n) + A024495(n) + A111927(n) = 2^n - 1. [Cournot, page 96 last formula, but misprint should be 2^x - 1 rather than 2^p - 1]. (End)
a(n) = C(n,1) + C(n,4) + ... + C(n, 3*floor(n/3)+1). - Jianing Song, Oct 04 2021
E.g.f.: exp(x/2)*(exp(3*x/2) - cos(sqrt(3)*x/2) + sqrt(3)*sin(sqrt(3)*x/2))/3. - Stefano Spezia, Feb 06 2025

A131531 Period 6: repeat [0, 0, 1, 0, 0, -1].

Original entry on oeis.org

0, 0, 1, 0, 0, -1, 0, 0, 1, 0, 0, -1, 0, 0, 1, 0, 0, -1, 0, 0, 1, 0, 0, -1, 0, 0, 1, 0, 0, -1, 0, 0, 1, 0, 0, -1, 0, 0, 1, 0, 0, -1, 0, 0, 1, 0, 0, -1, 0, 0, 1, 0, 0, -1, 0, 0, 1, 0, 0, -1, 0, 0, 1, 0, 0, -1, 0, 0, 1, 0, 0, -1, 0, 0, 1, 0, 0, -1, 0, 0, 1, 0, 0, -1, 0, 0, 1, 0, 0, -1, 0, 0

Offset: 1

Paul Curtz, Aug 26 2007

Also: partial sums of A092220 shifted by two indices. - R. J. Mathar, Feb 08 2008
From Paul Curtz, Jun 05 2011: (Start)
The square array of this sequence in the top row and further rows defined as first differences of preceding rows starts (see A167613):
.   0,   0,   1,   0,   0,  -1, ...
.   0,   1,  -1,   0,  -1,   1, ...  = A092220,
.   1,  -2,   1,  -1,   2,  -1, ...  = A131556,
.  -3,   3,  -2,   3,  -3    2, ...
.   6,  -5,   5,  -6,   5,  -5, ...
. -11,  10, -11,  11, -10,  11, ...
.  21, -21,  22, -21,  21, -22, ...
. -42,  43, -43,  42, -43,  43, ...
The main diagonal in this array is A001045; the first superdiagonal is the negated elements of A001045, the second superdiagonal is A078008.
The left column of the array is basically the inverse binomial transform, (-1)^n * A024495(n), assuming offset 0.
The second column of the array is A131708 with alternating signs, and the third column is A024493 with alternating signs (both assuming offset 0). (End)

Index entries for linear recurrences with constant coefficients, signature (0,0,-1).

Cf. A001045, A024493, A024495, A078008, A092220, A131556, A131708, A167613.

&cat[[0, 0, 1, 0, 0, -1]^^20]; // Wesley Ivan Hurt, Jun 20 2016

A131531:=n->[0, 0, 1, 0, 0, -1][(n mod 6)+1]: seq(A131531(n), n=0..100); # Wesley Ivan Hurt, Jun 20 2016

PadRight[{}, 120, {0,0,1,0,0,-1}] (* Harvey P. Dale, Nov 11 2012 *)

a(n)=[0,0,1,0,0,-1][n%6+1] \\ Charles R Greathouse IV, Jun 01 2011

G.f.: x^3/(x+1)/(x^2-x+1). - R. J. Mathar, Nov 14 2007
a(n) = (-A057079(n+1) - (-1)^n)/3. - R. J. Mathar, Jun 13 2011
a(n) = -cos(Pi*(n-1)/3)/3 + sin(Pi*(n-1)/3)/sqrt(3) - (-1)^n/3. - R. J. Mathar, Oct 08 2011
a(n) = ( (-1)^n - (-1)^floor((n+2)/3) )/2. - Bruno Berselli, Jul 09 2013
a(n) + a(n-3) = 0 for n > 3. - Wesley Ivan Hurt, Jun 20 2016

Edited by N. J. A. Sloane, Sep 15 2007

A024494 a(n) = C(n,1) + C(n,4) + ... + C(n, 3*floor(n/3) + 1).

Original entry on oeis.org

1, 2, 3, 5, 10, 21, 43, 86, 171, 341, 682, 1365, 2731, 5462, 10923, 21845, 43690, 87381, 174763, 349526, 699051, 1398101, 2796202, 5592405, 11184811, 22369622, 44739243, 89478485, 178956970, 357913941, 715827883, 1431655766, 2863311531, 5726623061, 11453246122

Offset: 1

Clark Kimberling

M^n * [1,0,0] = [A024493(n), A024495(n), a(n)], where M is 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 = A024493(n) + a(n)*M + A024495(n)*M^2. - Stanislav Sykora, Jun 10 2012

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

G. C. Greubel, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (3,-3,2).

Cf. A010892, A024493, A024495, A057079.

See A131708 for another version.

[n le 3 select n else 3*Self(n-1) -3*Self(n-2) +2*Self(n-3): n in [1..40]]; // G. C. Greubel, Jan 23 2023

nn=20;a=1/(1-x);Drop[CoefficientList[Series[a x /(1-x-x^3 a^2),{x,0,nn}],x],1] (* Geoffrey Critzer, Dec 22 2013 *)
LinearRecurrence[{3,-3,2}, {1,2,3}, 40] (* G. C. Greubel, Jan 23 2023 *)

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

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

def A024494(n): return (1/3)*(2^n -chebyshev_U(n,1/2) +2*chebyshev_U(n-1,1/2))
[A024494(n) for n in range(1,41)] # G. C. Greubel, Jan 23 2023

3*a(n) = 2^n + 2*cos( (n-2)*Pi/3 ) = 2^n - A057079(n+2).
G.f.: x*(1-x)/((1-2*x)*(1-x+x^2)). - Paul Barry, Feb 11 2004
a(n) = Sum_{k=0..n} 2^k*2*sin(-Pi*(n-k)/3 + Pi/3)/sqrt(3) (offset 0). - Paul Barry, May 18 2004
G.f.: (x*(1-x^2)*(1-x^3)/(1-x^6))/(1-2*x). - Michael Somos, Feb 14 2006
a(n+1) - 2*a(n) = A010892(n+1). - Michael Somos, Feb 14 2006
a(n) = 3*a(n-1) - 3*a(n-2) + 2*a(n-3). - Paul Curtz, Nov 20 2007
Equals binomial transform of (1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, ...). - Gary W. Adamson, Jul 03 2008
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) = y(n). - Stanislav Sykora, Jun 10 2012
E.g.f.: exp(x/2)*(exp(3*x/2) - cos(sqrt(3)*x/2) + sqrt(3)*sin(sqrt(3)*x/2))/3. - Stefano Spezia, Feb 06 2025

A139398 a(n) = Sum_{k >= 0} binomial(n,5*k).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 7, 22, 57, 127, 254, 474, 859, 1574, 3004, 6008, 12393, 25773, 53143, 107883, 215766, 427351, 843756, 1669801, 3321891, 6643782, 13333932, 26789257, 53774932, 107746282, 215492564, 430470899, 859595529, 1717012749, 3431847189, 6863694378

Offset: 0

N. J. A. Sloane, Jun 13 2008

From Gary W. Adamson, Mar 13 2009: (Start)
M^n * [1,0,0,0,0] = [a(n), A139761(n), A139748(n), A139714(n), A133476(n)]
where M = the 5 X 5 matrix [1,1,0,0,0; 0,1,1,0,0; 0,0,1,1,0; 0,0,0,1,1; 1,0,0,0,1]
Sum of terms = 2^n. Example: M^6 * [1,0,0,0,0] = [7, 15, 20, 15, 7]; sum = 2^6 = 64. (End)
{A139398, A133476, A139714, A139748, A139761} is the difference analog of the hyperbolic functions of order 5, {h_1(x), h_2(x), h_3(x), h_4(x), h_5 (x)}. For a definition see the reference "Higher Transcendental Functions" and the Shevelev link. - Vladimir Shevelev, Jun 14 2017

A. Erdelyi, Higher Transcendental Functions, McGraw-Hill, 1955, Vol. 3, Ch. 18.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
John B. Dobson, A matrix variation on Ramus's identity for lacunary sums of binomial coefficients, arXiv preprint arXiv:1610.09361 [math.NT], 2016.
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 (5,-10,10,-5,2).

Cf. A000749, A024493, A024494, A024495, A038503, A038504, A038505, A133476, A139714, A139748, A139761.

[n le 5 select 1 else 5*Self(n-1)-10*Self(n-2)+10*Self(n-3)-5*Self(n-4)+2*Self(n-5): n in [1..40]]; // Vincenzo Librandi, Jun 27 2017

f:=(n,r,a) -> add(binomial(n,r*k+a),k=0..n); fs:=(r,a)->[seq(f(n,r,a),n=0..40)];
A139398_list := proc(n) local i; (exp(z)^2+2*exp(3/4*z+1/4*z*sqrt(5))* cos(1/4*z*sqrt(2)*sqrt(5+sqrt(5)))+2*exp(3/4*z-1/4*z*sqrt(5))* cos(1/4*z*sqrt(2)*sqrt(5-sqrt(5))))/5; series(%,z,n+2): seq(simplify(i!*coeff(%,z,i)), i=0..n) end: A139398_list(35); # Peter Luschny, Jul 10 2012

LinearRecurrence[{5,-10,10,-5,2},{1,1,1,1,1},40] (* Harvey P. Dale, Jun 11 2015 *)
Expand@Table[(2^n + Sqrt[5] (Cos[Pi n/5] - (-1)^n Cos[2 Pi n/5]) Fibonacci[n] + (Cos[Pi n/5] + (-1)^n Cos[2 Pi n/5]) LucasL[n])/5, {n, 0, 20}] (* Vladimir Reshetnikov, Oct 04 2016 *)

G.f.: -(x-1)^4/((2*x-1)*(x^4-2*x^3+4*x^2-3*x+1)). - Maksym Voznyy (voznyy(AT)mail.ru), Aug 12 2009
E.g.f.: (exp(z)^2+2*exp(3/4*z+1/4*z*sqrt(5))*cos(1/4*z*sqrt(2)*sqrt(5+sqrt(5)))+ 2*exp(3/4*z-1/4*z*sqrt(5))*cos(1/4*z*sqrt(2)*sqrt(5-sqrt(5))))/5. - Peter Luschny, Jul 10 2012
a(n) = (2^n + sqrt(5)*(cos(Pi*n/5) - (-1)^n*cos(2*Pi*n/5))*A000045(n) + (cos(Pi*n/5) + (-1)^n*cos(2*Pi*n/5))*A000032(n))/5. - Vladimir Reshetnikov, Oct 04 2016
From Vladimir Shevelev, Jun 17 2017: (Start)
a(n) = round((2/5)*(2^(n-1) + phi^n*cos(Pi*n/5))), where phi is the golden ratio and round(x) is the integer nearest to x.
The formula follows from the identity a(n)=1/5*Sum_{j=1..5}((omega_5)^j + 1)^n, where omega_5=exp(2*Pi*i)/5 (cf. Theorem 1 of [Shevelev] link for i=1, n=5, m:=n). Further note that for a=cos(x)+i*sin(x), a+1 = 2*cos ^2 (x/2) + i*sin(x), and for the argument y of a+1 we have tan(y)=tan(x/2) and r^2 = 4*cos^4(x/2) + sin^2(x) = 4*cos^2(x/2). So (a+1)^n = (2*cos(x /2))^n*(cos(n*x/2) + i*sin(n*x/2)). Using this, for x=2*Pi/5, we have (omega_5+1)^n = phi^n(cos(Pi*n/5) + i*sin(Pi*n/5)). Since (omega_5)^4+1=(1+omega_5)/omega_5, we easily find that ((omega_5)^4+1)^n is conjugate to (omega_5+1)^n. So (omega_5+1)^n+((omega_5)^4+1)^n = phi^n*cos(Pi*n/5). Further, we similarly obtain that (omega_5)^2+1 is conjugate to (omega_5) ^3+1=(1+(omega_5)^2)/(omega_5)^2 and ((omega_5)^2+1)^n +((omega_5)^3+1)^n = 2*(sqrt(2-phi))^n*cos(2*Pi*n/5). The absolute value of the latter <= 2*(2-phi)^(n/2) and quickly tends to 0. Finally, ((omega_5)^5+1)^n=2^n, and the formula follows. (End)
a(n+m) = a(n)*a(m) + H_2(n)*H_5(m) + H_3(n)*H_4(m) + H_4(n)*H_3(m) + H_5(n)*H_2(m), where H_2=A133476, H_3=A139714, H_4=A139748, H_5=A139761. - Vladimir Shevelev, Jun 17 2017

A049016 Expansion of 1/((1-x)^5 - x^5).

Original entry on oeis.org

1, 5, 15, 35, 70, 127, 220, 385, 715, 1430, 3004, 6385, 13380, 27370, 54740, 107883, 211585, 416405, 826045, 1652090, 3321891, 6690150, 13455325, 26985675, 53971350, 107746282, 214978335, 429124630, 857417220, 1714834440, 3431847189

Offset: 0

N. J. A. Sloane

Seiichi Manyama, Table of n, a(n) for n = 0..3000
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,2).

Sequences of the form 1/((1-x)^m - x^m): A000079 (m=1,2), A024495 (m=3), A000749 (m=4), this sequence (m=5), A192080 (m=6), A049017 (m=7), A290995 (m=8), A306939 (m=9).

Cf. A000750, A078789.

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( 1/((1-x)^5-x^5) )); // G. C. Greubel, Apr 11 2023

CoefficientList[Series[1/((1-x)^5-x^5),{x,0,30}],x] (* or *) LinearRecurrence[ {5,-10,10,-5,2},{1,5,15,35,70},40] (* Harvey P. Dale, Jan 20 2014 *)

def A049016_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( 1/((1-x)^5-x^5) ).list()
A049016_list(30) # G. C. Greubel, Apr 11 2023

G.f.: 1/((1-x)^5-x^5) = 1/( (1-2*x)*(1-3*x+4*x^2-2*x^3+x^4) ).
a(10*n+3) = A078789(5*n+3).
a(10*n+5) = A078789(5*n+4).
a(n) = (-1)^n * A000750(n).
Binomial transform of expansion of (1+x)^4/(1-x^5), or (1, 4, 6, 4, 1, 1, 4, 6, 4, 1, ...). - Paul Barry, Mar 19 2004
a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + 2*a(n-5). - Paul Curtz, May 24 2008
G.f.: -1/( x^5 - 1 + 5*x/Q(0) ) where Q(k) = 1 + k*(x+1) + 5*x - x*(k+1)*(k+6)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Mar 15 2013

A369173 Irregular triangle read by rows: row n lists all of the distinct derivable strings in the MIU formal system that are n characters long.

Original entry on oeis.org

31, 301, 310, 311, 3001, 3010, 3011, 3100, 3101, 3110, 30001, 30010, 30011, 30100, 30101, 30110, 31000, 31001, 31010, 31100, 31111, 300001, 300010, 300011, 300100, 300101, 300110, 301000, 301001, 301010, 301100, 301111, 310000, 310001, 310010, 310100, 310111, 311000, 311011, 311101, 311110, 311111

Offset: 2

Paolo Xausa, Jan 15 2024

See A368946 for the description of the MIU formal system.
A string S can be derived in the MIU formal system if and only if S contains just one M (as its first character) and an arbitrary number of I and U characters, where the number of I characters is not divisible by 3 (see Wikipedia link).
Strings are encoded using the map M -> 3, I -> 1 and U -> 0, and then sorted.
Row n has length A024495(n).

			Triangle begins:
  [2] 31;
  [3] 301 310 311;
  [4] 3001 3010 3011 3100 3101 3110;
  [5] 30001 30010 30011 30100 30101 30110 31000 31001 31010 31100 31111;
  ...

Douglas R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979, pp. 33-41 and pp. 261-262.

Paolo Xausa, Table of n, a(n) for n = 2..10922 (rows 2..14 of the triangle, flattened).
Wikipedia, MU Puzzle.
Index entries for sequences from "Goedel, Escher, Bach".

Cf. A368946, A024495 (row lengths), A369174 (number of zeros), A369179 (number of ones), A369409.

Cf. A369586 (shortest proofs), A369408 (length of shortest proofs), A369587 (number of symbols of shortest proofs).

A369173row[n_] := Map[FromDigits[Join[{3}, #]]&, Select[Tuples[{0, 1}, n - 1], !Divisible[Count[#, 1], 3]&]]; Array[A369173row, 5, 2]

cp's OEIS Frontend

A079309 a(n) = C(1,1) + C(3,2) + C(5,3) + ... + C(2*n-1,n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

Formula

A038503 Sum of every 4th entry of row n in Pascal's triangle, starting at "n choose 0".

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A131534 Period 3: repeat [1, 2, 1].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A131708 A024494 prefixed by a 0.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

A131531 Period 6: repeat [0, 0, 1, 0, 0, -1].

Views

Author

Keywords

Comments

Links

Crossrefs