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