OFFSET
0,4
COMMENTS
Number of strings over Z_2 of length n with trace 0 and subtrace 1.
Same as number of strings over GF(2) of length n with trace 0 and subtrace 1.
Binomial transform of (0,1,1,0,0,1,1,0,...) gives a(n) for n >= 1. - Paul Barry, Jul 07 2003
From Gary W. Adamson, Mar 13 2009: (Start)
M^n * [1,0,0,0] = [A038503(n), A000749(n), a(n), A038504(n)]; where M = a 4 X 4 matrix [1,1,0,0; 0,1,1,0; 0,0,1,1; 1,0,0,1]. Sum of terms = 2^n.
Example: M^6 * [1,0,0,0] [16, 20, 16, 12]; sum = 2^6 = 64. (End)
{A038503, A038504, A038505, A000749} is the difference analog of the hyperbolic functions of order 4, {h_1(x), h_2(x), h_3(x), h_4(x)}. For a definition of {h_i(x)} and the difference analog {H_i (n)} see [Erdelyi] and the Shevelev link respectively. - Vladimir Shevelev, Jun 14 2017
REFERENCES
A. Erdelyi, Higher Transcendental Functions, McGraw-Hill, 1955, Vol. 3, Chapter XVIII.
LINKS
Peter Luschny, Table of n, a(n) for n = 0..1000
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
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.
a(n) = Sum_{k=0..n} binomial(n, 2 + 4*k), n >= 0.
a(n) = Sum_{k=0..n} (1/2)*C(n, k)*(-1)^C(k+3, 3) for n >= 1. - Paul Barry, Jul 07 2003
From Paul Barry, Nov 29 2004: (Start)
G.f.: x^2*(1-x)/((1-x)^4-x^4) = x^2*(1-x)/((1-2*x)*(1-2*x+2*x^2));
a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2*k)*(1-(-1)^k)/2. (End)
a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3), n > 3; sequence is identical to its fourth differences. - Paul Curtz, Dec 21 2007
a(n+m) = a(n)*H_1(m) + H_2(n)*H_2(m) + H_1(n)*a(m) + H_4(n)*H_4(m),
From Peter Luschny, Jun 15 2017: (Start)
a(n) = n! [x^n] (1 + exp(2*x) - 2*exp(x)*cos(x))/4.
a(n) = (2^n - (1-i)^n - (1+i)^n) / 4 for n >= 1. Compare V. Shevelevs' formula (1) in A000749. (End)
From Vladimir Shevelev, Jun 16 2017: (Start)
Proof of the conjecture by Creighton Dement (May 22 2005): using the first formula of Theorem 1 in [Shevelev link] for n=4, omega=i=sqrt(-1), i:=1,2,3,4, m:=n>=1, we have
a(n) = (1/2)*(2^(n-1)-2^(n/2)*cos(Pi*n/4)), A038504(n) = (1/2)*(2^(n-1)+2^(n/2)* sin(Pi*n/4)), A000749(n) = (1/2)*(2^(n-1)-2^(n/2)*sin(Pi*n/4)). Finally we use the formula by Paul Barry: A009545(n) = 2^(n/2)*sin(Pi*n/4) = 2^(n/2)*(-cos(Pi*(n+2)/4)). Now it is easy to obtain the hypothetical formula. (End)
EXAMPLE
a(3; 0, 1) = 3 since the three binary strings of trace 0, subtrace 1 and length 3 are { 011, 101, 110 }.
MAPLE
# From Peter Luschny, Jun 15 2017: (Start)
s := sqrt(2): h := n -> [-2, -s, 0, s, 2, s, 0, -s][1 + (n mod 8)]:
a := n -> `if`(n=0, 0, (2^n + 2^(n/2)*h(n))/4): seq(a(n), n=0..32);
# Alternatively:
egf := (1 + exp(2*x) - 2*exp(x)*cos(x))/4:
series(egf, x, 33): seq(n!*coeff(%, x, n), n=0..32); # (End)
MATHEMATICA
LinearRecurrence[{4, -6, 4}, {0, 0, 1, 3}, 40] (* Vincenzo Librandi, Jun 22 2012 *)
Table[If[n==0, 0, 2^(n-2) - 2^(n/2-1) Cos[Pi*n/4]], {n, 0, 32}] (* Vladimir Reshetnikov, Sep 16 2016 *)
PROG
(Magma) I:=[0, 0, 1, 3]; [n le 3 select I[n] else 4*Self(n-1)-6*Self(n-2)+4*Self(n-3): n in [1..40]]; // Vincenzo Librandi, Jun 22 2012
(Haskell)
a038505 n = a038505_list !! n
a038505_list = tail $ zipWith (-) (tail a000749_list) a000749_list
-- Reinhard Zumkeller, Jul 15 2013
(Sage)
A = lambda n: (2^n - (1-I)^n - (1+I)^n) / 4 if n != 0 else 0
print([A(n) for n in (0..32)]) # Peter Luschny, Jun 16 2017
(GAP) List([0..35], n->Sum([0..n], k->Binomial(n, 2+4*k))); # Muniru A Asiru, Feb 21 2019
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
EXTENSIONS
Missing 0 prepended by Vladimir Shevelev, Jun 14 2017
Edited by Peter Luschny, Jun 16 2017
STATUS
approved