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
KEYWORD
easy,nonn
AUTHOR
STATUS
approved