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

%I #77 May 10 2023 12:17:27

%S 1,1,1,1,2,6,16,36,72,136,256,496,992,2016,4096,8256,16512,32896,

%T 65536,130816,261632,523776,1048576,2098176,4196352,8390656,16777216,

%U 33550336,67100672,134209536,268435456,536887296,1073774592,2147516416,4294967296,8589869056,17179738112

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

%C Number of strings over Z_2 of length n with trace 0 and subtrace 0.

%C Same as number of strings over GF(2) of length n with trace 0 and subtrace 0.

%C 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

%C 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

%C {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

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

%D 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.

%H Seiichi Manyama, <a href="/A038503/b038503.txt">Table of n, a(n) for n = 0..3000</a>

%H Paul Barry, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Barry/barry84.html">A Catalan Transform and Related Transformations on Integer Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5, pp. 1-24.

%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 Frank Ruskey, <a href="http://combos.org/TSstringZ2">Strings over Z_2 with given trace and subtrace</a>

%H Frank Ruskey, <a href="http://combos.org/TSstringF2">Strings over GF(2) with given trace and subtrace</a>

%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 (4,-6,4).

%F From _Paul Barry_, Mar 18 2004: (Start)

%F G.f.: (1-x)^3/((1-x)^4-x^4);

%F 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)

%F 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

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

%F a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2k)(1+(-1)^k)/2. - _Paul Barry_, Nov 29 2004

%F 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.

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

%F From _Vladimir Shevelev_, Aug 01 2017: (Start)

%F For n >= 1, {H_i(n)} are linearly dependent sequences: a(n) = H_1(n) = H_2(n) - H_3(n) + H_4(n);

%F 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.

%F For proofs, see Shevelev's link, Theorems 2, 3. (End)

%F 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

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

%p A038503_list := proc(n) local i; series(exp(z)*(cosh(z)+cos(z))/2,z,n+2):

%p seq(i!*coeff(%,z,i),i=0..n) end: A038503_list(32); # _Peter Luschny_, Jul 10 2012

%p a := n -> hypergeom([1/4 - n/4, 1/2 - n/4, 3/4 - n/4, -n/4], [1/4, 1/2, 3/4], 1):

%p seq(simplify(a(n)), n = 0..36); # _Peter Luschny_, Mar 18 2023

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

%t Join[{1},LinearRecurrence[{4,-6,4},{1,1,1},40]] (* _Harvey P. Dale_, Dec 02 2014 *)

%o (PARI) a(n) = sum(k=0, n\4, binomial(n, 4*k)); \\ _Michel Marcus_, Mar 13 2019

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

%Y Row sums of A098173.

%K easy,nonn

%O 0,5

%A _Frank Ruskey_