0,5

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.

Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), Mar 13 2009: (Start)

M^n = [1,0,0,0] = [a(n), A000749(n), A038505(n-1), A038504(n)]; where M = the

4x4 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. (End)

Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

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.

Index entries for sequences related to linear recurrences with constant coefficients

F. Ruskey, Strings over Z_2 of given Trace and Subtrace

F. Ruskey, Strings over GF(2) of given Trace and Subtrace

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)). - Paul Barry (pbarry(AT)wit.ie), Mar 18 2004

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 (pbarry(AT)wit.ie), Jul 25 2004

a(n)=sum{k=0..n, binomial(n, 4(n-k))} - Paul Barry (pbarry(AT)wit.ie), Aug 30 2004

a(n)=sum{k=0..floor(n/2), binomial(n, 2k)(1+(-1)^k)/2} - Paul Barry (pbarry(AT)wit.ie), 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.

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

ZL:=[S, {a = Atom, b = Atom, S = Prod(X, Sequence(Prod(X, X, X, X))), X = Sequence(b, card >= 1)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=1..33); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Mar 26 2008

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

Row sums of A098173

Sequence in context: A159938 A145126 A005676 this_sequence A079990 A127902 A157136

Adjacent sequences: A038500 A038501 A038502 this_sequence A038504 A038505 A038506

easy,nonn

Frank Ruskey (fruskey(AT)cs.uvic.ca)