|
%I M3383 N1364 #140 Apr 12 2023 08:06:31
%S 0,0,0,1,4,10,20,36,64,120,240,496,1024,2080,4160,8256,16384,32640,
%T 65280,130816,262144,524800,1049600,2098176,4194304,8386560,16773120,
%U 33550336,67108864,134225920,268451840,536887296,1073741824,2147450880
%N 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.
%C Number of strings over Z_2 of length n with trace 1 and subtrace 1.
%C Same as number of strings over GF(2) of length n with trace 1 and subtrace 1.
%C Also expansion of bracket function.
%C 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
%C From _Gary W. Adamson_, Mar 13 2009: (Start)
%C M^n * [1,0,0,0] = [A038503(n), a(n), A038505(n), A038504(n)];
%C where M = the 4 X 4 matrix [1,1,0,0; 0,1,1,0; 0,0,1,1; 1,0,0,1].
%C Sum of the 4 terms = 2^n.
%C Example; M^6 * [1,0,0,0] = [16, 20, 16, 12] sum = 64 = 2^6. (End)
%C 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
%C {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
%C This is the p-INVERT of (1,1,1,1,1,...) for p(S) = 1 - S^4; see A291000. - _Clark Kimberling_, Aug 24 2017
%D Higher Transcendental Functions, Bateman Manuscript Project, Vol. 3, ed. A. Erdelyi, 1983 (chapter XVIII).
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A000749/b000749.txt">Table of n, a(n) for n = 0..200</a>
%H H. W. Gould, <a href="http://www.fq.math.ca/Scanned/2-4/gould.pdf">Binomial coefficients, the bracket function and compositions with relatively prime summands</a>, Fib. Quart. 2(4) (1964), 241-260.
%H Maran van Heesch, <a href="http://alexandria.tue.nl/extra1/afstversl/wsk-i/heesch2014.pdf">The multiplicative complexity of symmetric functions over a field with characteristic p</a>, Thesis, 2014.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.
%H F. Ruskey, <a href="http://combos.org/TSstringZ2">Strings over Z_2 with given trace and subtrace</a>
%H F. Ruskey, <a href="http://combos.org/TSstringF2">Strings over GF(2) with given trace and subtrace</a>
%H Vladimir Shevelev, <a href="https://arxiv.org/abs/1706.01454">Combinatorial identities generated by difference analogs of hyperbolic and trigonometric functions of order n</a>, arXiv:1706.01454 [math.CO], 2017.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,-6,4).
%F G.f.: x^3/((1-x)^4 - x^4).
%F a(n) = Sum_{k=0..n} binomial(n, 4*k+3).
%F a(n) = a(n-1) + A038505(n-2) = 2*a(n-1) + A009545(n-2) for n>=2.
%F Without the two initial zeros, binomial transform of A007877. - _Henry Bottomley_, Jun 04 2001
%F From _Paul Barry_, Aug 30 2004: (Start)
%F a(n) = (2^n - 2^(n/2+1)*sin(Pi*n/4) - 0^n)/4.
%F a(n+1) is the binomial transform of A021913. (End)
%F 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.
%F 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
%F From _Vladimir Shevelev_, Jun 14 2017: (Start)
%F 1) For n>=1, a(n) = (1/4)*(2^n + i*(1+i)^n - i*(1-i)^n), where i=sqrt(-1);
%F 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),
%F where H_1 = A038503, H_2 = A038504, H_3 = A038505. (End)
%F a(n) = (2^n - 2*A009545(n) - [n=0])/4. - _G. C. Greubel_, Apr 11 2023
%e a(4;1,1)=4 since the four binary strings of trace 1, subtrace 1 and length 4 are { 0111, 1011, 1101, 1110 }.
%p A000749 := proc(n) local k; add(binomial(n,4*k+3),k=0..floor(n/4)); end;
%p A000749:=-1/((2*z-1)*(2*z**2-2*z+1)); # _Simon Plouffe_ in his 1992 dissertation
%p 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
%p # Alternatively:
%p s := sqrt(2): h := n -> [0,-s,-2,-s,0,s,2,s][1+(n mod 8)]:
%p a := n -> `if`(n=0,0,(2^n+2^(n/2)*h(n))/4):
%p seq(a(n),n=0..33); # _Peter Luschny_, Jun 14 2017
%t Join[{0},LinearRecurrence[{4,-6,4},{0,0,1},40]] (* _Harvey P. Dale_, Mar 31 2012 *)
%t CoefficientList[Series[x^3/(1 -4x +6x^2 -4x^3), {x,0,80}], x] (* _Vincenzo Librandi_, Dec 31 2015 *)
%o (PARI) a(n)=sum(k=0,n\4,binomial(n,4*k+3))
%o (Haskell)
%o a000749 n = a000749_list !! n
%o a000749_list = 0 : 0 : 0 : 1 : zipWith3 (\u v w -> 4 * u - 6 * v + 4 * w)
%o (drop 3 a000749_list) (drop 2 a000749_list) (drop 1 a000749_list)
%o -- _Reinhard Zumkeller_, Jul 15 2013
%o (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
%o (SageMath)
%o @CachedFunction
%o def a(n): # a = A000749
%o if (n<4): return (n//3)
%o else: return 4*a(n-1) -6*a(n-2) +4*a(n-3)
%o [a(n) for n in range(41)] # _G. C. Greubel_, Apr 11 2023
%Y Cf. A000748, A000750, A001659, A006090, A007877, A009545, A011765.
%Y Cf. A021913, A038503, A038504, A038505, A133209, A133212, A291000.
%Y 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).
%K nonn,easy,nice
%O 0,5
%A _N. J. A. Sloane_
%E Additional comments from Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Nov 22 2002
%E New definition from _Paul Curtz_, Oct 29 2007
%E Edited by _N. J. A. Sloane_, Jun 13 2008
|
