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

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,5

Comments

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

References

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.

Links

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

Formula

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

Example

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

Maple

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

Mathematica

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

Prog

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

Crossrefs

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

Row sums of A098173.

Sequence in context: A005676 A365735 A365079 * A352066 A351971 A365245

Adjacent sequences: A038500 A038501 A038502 * A038504 A038505 A038506

Keyword

easy,nonn

Author

Frank Ruskey

Status

approved