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.

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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

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

Examples

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

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

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

Programs

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

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

PARI

a(n)=sum(k=0,n\4,binomial(n,4*k+3))

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

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

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