A038505 Sum of every 4th entry of row n in Pascal's triangle, starting at binomial(n,2).

0, 0, 1, 3, 6, 10, 16, 28, 56, 120, 256, 528, 1056, 2080, 4096, 8128, 16256, 32640, 65536, 131328, 262656, 524800, 1048576, 2096128, 4192256, 8386560, 16777216, 33558528, 67117056, 134225920, 268435456, 536854528, 1073709056

Offset: 0

Author

Frank Ruskey

Keywords

• easy
• nonn

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

Examples

			a(3; 0, 1) = 3 since the three binary strings of trace 0, subtrace 1 and length 3 are { 011, 101, 110 }.
		

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
• F. Ruskey, Strings over Z_2 with given trace and subtrace
• F. 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).

Crossrefs

Cf. A000749, A009116, A009545, A038503, A038504.

Programs

GAP

List([0..35],n->Sum([0..n],k->Binomial(n,2+4*k))); # Muniru A Asiru, Feb 21 2019

Haskell

a038505 n = a038505_list !! n
a038505_list = tail $ zipWith (-) (tail a000749_list) a000749_list
-- Reinhard Zumkeller, Jul 15 2013

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

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

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

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)

Conjecture: 2*a(n+2) = A038504(n+2) + A000749(n+2) + 2*A009545(n). - Creighton Dement, May 22 2005

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) = A000749(n+1) - A000749(n). - Reinhard Zumkeller, Jul 15 2013

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),

where H_1=A038503, H_2=A038504, H_4=A000749. - Vladimir Shevelev, Jun 14 2017

From Peter Luschny, Jun 15 2017: (Start)

a(n) = n! [x^n] (1 + exp(2*x) - 2*exp(x)*cos(x))/4.

a(n) = A038503(n+2) - 2*A038503(n+1) + A038503(n).

a(n) = 2^(n-2) - A046980(n)*2^(A004525(n-3)) for n >= 1.

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)

Extensions

Missing 0 prepended by Vladimir Shevelev, Jun 14 2017

Edited by Peter Luschny, Jun 16 2017