|
| |
|
|
A053545
|
|
Comparison's needed for Batcher's sorting algorithm applied to 2^n items.
|
|
5
| |
|
|
0, 1, 5, 19, 63, 191, 543, 1471, 3839, 9727, 24063, 58367, 139263, 327679, 761855, 1753087, 3997695, 9043967, 20316159, 45350911, 100663295, 222298111, 488636415, 1069547519, 2332033023, 5066719231, 10972299263, 23689428991
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| Appears to be number of edges in graph where nodes are binary vectors of length n, two nodes u, v being joined by an edge if there's a vector of length n-1 that can be reached from u by deleting a bit and from v by deleting a bit. An independent set in this graph is a code that will correct single deletions.
Binomial transform of A005893: (1, 4, 10, 20, 34, 52, 74,...) = (1, 5, 19, 63, 191,...). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 28 2008
Let A be the Hessenberg matrix of order n defined by: A[1,j]=1, A[i,i]:=2,(i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=2, a(n-1)= (-1)^n*coeff(charpoly(A,x),x^2). [From Milan R. Janjic (agnus(AT)blic.net), Jan 26 2010]
|
|
|
LINKS
| Vincenzo Librandi, Table of n, a(n) for n = 0..3000
I. Wegener, The Complexity of Boolean Functions, Wiley, 1987, see p. 151, (2.7).
|
|
|
FORMULA
| G.f.: x*(1-2x+2x^2)/((1-x)*(1-2x)^3).
a(n)=2^(n-2)*(n^2-n+4)-1.
|
|
|
PROG
| (MAGMA) [2^(n-2)*(n^2-n+4)-1: n in [0..30]]; // vincenzo Librandi, Oct 10 2011
|
|
|
CROSSREFS
| The size of a maximal independent set in this graph (1, 1, 2, 2, 4, 6, 10, ...) agrees with A000016 for n <= 7 (and probably for n=8).
Cf. A005893.
Sequence in context: A143131 A036677 A003296 * A049612 A001870 A025568
Adjacent sequences: A053542 A053543 A053544 * A053546 A053547 A053548
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), Mar 21 2000
|
| |
|
|
