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

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

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

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

Example

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

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

Prog

(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
(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

Crossrefs

Cf. A000749, A038503, A038504, A038505, A099855.

Sequence in context: A363670 A078495 A161701 * A352904 A275448 A018405

Adjacent sequences: A038501 A038502 A038503 * A038505 A038506 A038507

Keyword

easy,nonn

Author

Frank Ruskey

Status

approved