A038504 Sum of every 4th entry of row n in Pascal's triangle, starting at "n choose 1".

0, 1, 2, 3, 4, 6, 12, 28, 64, 136, 272, 528, 1024, 2016, 4032, 8128, 16384, 32896, 65792, 131328, 262144, 523776, 1047552, 2096128, 4194304, 8390656, 16781312, 33558528, 67108864, 134209536, 268419072, 536854528, 1073741824

Offset: 0

Author

Frank Ruskey

Keywords

• easy
• nonn

Comments

Number of strings over Z_2 of length n with trace 1 and subtrace 0.

Same as number of strings over GF(2) of length n with trace 1 and subtrace 0.

From Gary W. Adamson, Mar 13 2009: (Start)

M^n * [1,0,0,0] = [A038503(n), A000749(n), A038505(n), a(n)]; where

M = a 4x4 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 {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, Jul 31 2017

Examples

			a(2;1,0) = 3 since the two binary strings of trace 1, subtrace 0 and length 2 are { 10, 01 }.
		

References

• A. Erdelyi, Higher Transcendental Functions, McGraw-Hill, 1955, Vol. 3, Chapter XVIII.

Links

• Vincenzo Librandi, 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, A038503, A038504, A038505, A099855.

Programs

Magma

[0] cat [n le 3 select n else 4*Self(n-1) -6*Self(n-2) + 4*Self(n-3): n in [1..40]]; // Vincenzo Librandi, Jun 22 2012

Mathematica

CoefficientList[Series[x(1-x)^2/((1-2x)(1-2x+2x^2)),{x,0,40}],x] (* Vincenzo Librandi, Jun 22 2012 *)
LinearRecurrence[{4,-6,4},{0,1,2,3},40] (* Harvey P. Dale, Aug 23 2017 *)

SageMath

@CachedFunction
def a(n): # a = A038504
    if (n<4): return n
    else: return 4*a(n-1) - 6*a(n-2) + 4*a(n-3)
[a(n) for n in range(51)] # G. C. Greubel, Apr 20 2023

Formula

a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3), n > 3. - Paul Curtz, Mar 01 2008

G.f.: x*(1-x)^2/((1-2*x)*(1-2*x+2*x^2)).

From Paul Barry, Jul 25 2004: (Start)

Binomial transform of x/(1-x^4).

G.f.: x*(1-x)^2/((1-x)^4 - x^4) = x/(1-2*x) - x^3/((1-x)^4 - x^4).

a(n) = Sum_{k=0..floor(n/4)} binomial(n, 4*k+1).

a(n) = Sum_{k=0..n} binomial(n, k)*(sin(Pi*k/2)/2 + (1 - (-1)^k)/4).

a(n) = 2^(n-2) + 2^((n-2)/2)*sin(Pi*n/4) - 0^n/4. (End)

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.

(1, 2, 3, 4, 6, ...) is the binomial transform of (1, 1, 0, 0, 1, 1, ...). - Gary W. Adamson, May 15 2007

From Vladimir Shevelev, Jul 31 2017: (Start)

For n >= 1, {H_i(n)} are linearly dependent sequences: a(n) = H_2(n) = H_1(n) + H_3(n) - H_4(n);

a(n+m) = a(n)*H_1(m) + H_1(n)*a(m) + H_4(n)*H_3(m) + H_3(n)*H_4(m), where H_1 = A038503, H_3 = A038505, H_4 = A000749.

For proofs, see Shevelev's link, Theorems 2, 3. (End)

a(n) = (1/4)*(2^((n+1)/2)*ChebyshevU(n-1, 1/sqrt(2)) + 2^n - [n=0]). - G. C. Greubel, Apr 20 2023