|
Search: id:A053545
|
|
|
| A053545 |
|
Comparison's needed for Batcher's sorting algorithm applied to 2^n items. |
|
+0
4
|
|
| 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; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
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
|
|
LINKS
|
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.
|
|
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 this_sequence A049612 A001870 A025568
Adjacent sequences: A053542 A053543 A053544 this_sequence A053546 A053547 A053548
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com), Mar 21 2000
|
|
|
Search completed in 0.002 seconds
|
