|
|
A053545
|
|
Comparisons 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, 51002736639, 109521666047, 234612588543, 501437431807
(list;
graph;
refs;
listen;
history;
text;
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, 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). - Milan Janjic, Jan 26 2010
|
|
LINKS
|
|
|
FORMULA
|
G.f.: x*(1-2x+2x^2)/((1-x)*(1-2x)^3).
a(n) = 2^(n-2)*(n^2-n+4)-1.
a(n) = 7*a(n-1) - 18*a(n-2) + 20*a(n-3) - 8*a(n-4); a(0)=0, a(1)=1, a(2)=5, a(3)=19. - Harvey P. Dale, Apr 03 2013
|
|
MAPLE
|
|
|
MATHEMATICA
|
Table[2^(n-2)(n^2-n+4)-1, {n, 0, 30}] (* or *) LinearRecurrence[{7, -18, 20, -8}, {0, 1, 5, 19}, 30] (* Harvey P. Dale, Apr 03 2013 *)
|
|
PROG
|
|
|
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).
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|