A000749 a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3), n > 3, with a(0)=a(1)=a(2)=0, a(3)=1. (Formerly M3383 N1364)

0, 0, 0, 1, 4, 10, 20, 36, 64, 120, 240, 496, 1024, 2080, 4160, 8256, 16384, 32640, 65280, 130816, 262144, 524800, 1049600, 2098176, 4194304, 8386560, 16773120, 33550336, 67108864, 134225920, 268451840, 536887296, 1073741824, 2147450880

Offset

0,5

Comments

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

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

Also expansion of bracket function.

a(n) is also the number of induced subgraphs with odd number of edges in the complete graph K(n-1). - Alessandro Cosentino (cosenal(AT)gmail.com), Feb 02 2009

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

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

where M = the 4 X 4 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 * [1,0,0,0] = [16, 20, 16, 12] sum = 64 = 2^6. (End)

Binomial transform of the period 4 repeat: [0,0,0,1], which is the same as A011765 with offset 0. - Wesley Ivan Hurt, Dec 30 2015

{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 see the reference "Higher Transcendental Functions" and the Shevelev link. - Vladimir Shevelev, Jun 14 2017

This is the p-INVERT of (1,1,1,1,1,...) for p(S) = 1 - S^4; see A291000. - Clark Kimberling, Aug 24 2017

References

Higher Transcendental Functions, Bateman Manuscript Project, Vol. 3, ed. A. Erdelyi, 1983 (chapter XVIII).

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

T. D. Noe, Table of n, a(n) for n = 0..200

H. W. Gould, Binomial coefficients, the bracket function and compositions with relatively prime summands, Fib. Quart. 2(4) (1964), 241-260.

Maran van Heesch, The multiplicative complexity of symmetric functions over a field with characteristic p, Thesis, 2014.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.

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

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

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

a(n) = a(n-1) + A038505(n-2) = 2*a(n-1) + A009545(n-2) for n>=2.

Without the two initial zeros, binomial transform of A007877. - Henry Bottomley, Jun 04 2001

From Paul Barry, Aug 30 2004: (Start)

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

a(n+1) is the binomial transform of A021913. (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.

Without the initial three zeros, = binomial transform of [1, 3, 3, 1, 1, 3, 3, 1, 1, 3, 3, 1, 1, 3, 3, 1, 3, ...]. - Gary W. Adamson, Jun 19 2008

From Vladimir Shevelev, Jun 14 2017: (Start)

1) For n>=1, a(n) = (1/4)*(2^n + i*(1+i)^n - i*(1-i)^n), where i=sqrt(-1);

2) a(n+m) = a(n)*H_1(m) + H_3(n)*H_2(m) + H_2(n)*H_3(m) + H_1(n)*a(m),

where H_1 = A038503, H_2 = A038504, H_3 = A038505. (End)

a(n) = (2^n - 2*A009545(n) - [n=0])/4. - G. C. Greubel, Apr 11 2023

Example

a(4;1,1)=4 since the four binary strings of trace 1, subtrace 1 and length 4 are { 0111, 1011, 1101, 1110 }.

Maple

A000749 := proc(n) local k; add(binomial(n, 4*k+3), k=0..floor(n/4)); end;
A000749:=-1/((2*z-1)*(2*z**2-2*z+1)); # Simon Plouffe in his 1992 dissertation
a:= n-> if n=0 then 0 else (Matrix(3, (i, j)-> if (i=j-1) then 1 elif j=1 then [4, -6, 4][i] else 0 fi)^(n-1))[1, 3] fi: seq(a(n), n=0..33); # Alois P. Heinz, Aug 26 2008
# Alternatively:
s := sqrt(2): h := n -> [0, -s, -2, -s, 0, s, 2, s][1+(n mod 8)]:
a := n -> `if`(n=0, 0, (2^n+2^(n/2)*h(n))/4):
seq(a(n), n=0..33); # Peter Luschny, Jun 14 2017

Mathematica

Join[{0}, LinearRecurrence[{4, -6, 4}, {0, 0, 1}, 40]] (* Harvey P. Dale, Mar 31 2012 *)
CoefficientList[Series[x^3/(1 -4x +6x^2 -4x^3), {x, 0, 80}], x] (* Vincenzo Librandi, Dec 31 2015 *)

Prog

(PARI) a(n)=sum(k=0, n\4, binomial(n, 4*k+3))
(Haskell)
a000749 n = a000749_list !! n
a000749_list = 0 : 0 : 0 : 1 : zipWith3 (\u v w -> 4 * u - 6 * v + 4 * w)
   (drop 3 a000749_list) (drop 2 a000749_list) (drop 1 a000749_list)
-- Reinhard Zumkeller, Jul 15 2013
(Magma) I:=[0, 0, 0, 1]; [n le 4 select I[n] else 4*Self(n-1)-6*Self(n-2)+4*Self(n-3): n in [1..40]]; // Vincenzo Librandi, Dec 31 2015
(SageMath)
@CachedFunction
def a(n): # a = A000749
    if (n<4): return (n//3)
    else: return 4*a(n-1) -6*a(n-2) +4*a(n-3)
[a(n) for n in range(41)] # G. C. Greubel, Apr 11 2023

Crossrefs

Cf. A000748, A000750, A001659, A006090, A007877, A009545, A011765.

Cf. A021913, A038503, A038504, A038505, A133209, A133212, A291000.

Sequences of the form 1/((1-x)^m - x^m): A000079 (m=1,2), A024495 (m=3), this sequence (m=4), A049016 (m=5), A192080 (m=6), A049017 (m=7), A290995 (m=8), A306939 (m=9).

Sequence in context: A063758 A131924 A143982 * A360046 A354696 A369851

Adjacent sequences: A000746 A000747 A000748 * A000750 A000751 A000752

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

Additional comments from Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Nov 22 2002

New definition from Paul Curtz, Oct 29 2007

Edited by N. J. A. Sloane, Jun 13 2008

Status

approved