login
This site is supported by donations to The OEIS Foundation.

 

Logo

"Email this user" was broken Aug 14 to 9am Aug 16. If you sent someone a message in this period, please send it again.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000749 a(n) = 4a(n-1) - 6a(n-2) + 4a(n-3), n > 3, with a(0)=a(1)=a(2)=0, a(3)=1.
(Formerly M3383 N1364)
31
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 (list; graph; refs; listen; history; text; internal format)
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

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.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

F. Ruskey, Strings over Z_2 of given Trace and Subtrace

F. Ruskey, Strings over GF(2) of 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) = 2a(n-1) + A009545(n-2) for n>=2.

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

a(n) = 2^n/4 - 2^(n/2)sin(Pi*n/4)/2 - 0^n/4. a(n+1) is the binomial transform of A021913. - Paul Barry, Aug 30 2004

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

a(n) = -(1/4)*[(1+I)*(1-I)^(n-1)-(1-I)*(1+I)^(n-1)]+(1/2)*2^(n-1),100)-(1/4)*(C(2*n,n) mod 2), with n>=0. - Paolo P. Lava, Jun 29 2009

G.f.: -x^3/( x^4 - 1 + 4*x/Q(0) ) where Q(k) = 1 + k*(x+1) + 4*x - x*(k+1)*(k+5)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Mar 15 2013

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. - Vladimir Shevelev, Jun 14 2017

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 - 4 x + 6 x^2 - 4 x^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

CROSSREFS

Cf. A000748, A000750, A001659, A006090, A011765, A038503, A038504, A038505.

Cf. A133209, A133212.

Sequence in context: A063758 A131924 A143982 * A275934 A008058 A188280

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 21 00:45 EDT 2017. Contains 290855 sequences.