|
| |
|
|
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)
|
|
26
| |
|
|
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; 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). [From Alessandro Cosentino (cosenal(AT)gmail.com), Feb 02 2009]
Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), Mar 13 2009: (Start)
M^n * [1,0,0,0] = [A038503(n), a(n), A038505(n-1), A038504(n)]; where M =
a 4x4 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)
|
|
|
REFERENCES
| H. W. Gould, Binomial coefficients, the bracket function and compositions with relatively prime summands, Fib. Quart. 2 (1964), 241-260.
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
S. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
F. Ruskey, Strings over Z_2 of given Trace and Subtrace
F. Ruskey, Strings over GF(2) of given Trace and Subtrace
Index entries for sequences related to linear recurrences with constant coefficients
|
|
|
FORMULA
| G.f.: x^3/((1-x)^4-x^4). a(n) = Sum_{k=0..n} C(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 (se16(AT)btinternet.com), 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 (pbarry(AT)wit.ie), 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 (qntmpkt(AT)yahoo.com), 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 [From Paolo P. Lava (paoloplava(AT)gmail.com), Jun 29 2009]
|
|
|
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)); [Conjectured by S. 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); [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Aug 26 2008]
|
|
|
PROG
| (PARI) a(n)=sum(k=0, n\4, binomial(n, 4*k+3)).
|
|
|
CROSSREFS
| Cf. A000748, A000750, A001659, A006090, A038503, A038504, A038505.
Cf. A038503, A133209, A133212.
Sequence in context: A063758 A131924 A143982 * A008058 A188280 A038420
Adjacent sequences: A000746 A000747 A000748 * A000750 A000751 A000752
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Additional comments from Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Nov 22 2002
New definition from Paul Curtz (bpcrtz(AT)free.fr), Oct 29 2007
Edited by N. J. A. Sloane (njas(AT)research.att.com), Jun 13 2008
|
| |
|
|
