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 = 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
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
KEYWORD
easy,nonn
AUTHOR
STATUS
approved