The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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) 43
 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 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 A275934 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 27 10:09 EDT 2023. Contains 365688 sequences. (Running on oeis4.)