A053545 Comparisons needed for Batcher's sorting algorithm applied to 2^n items.

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

Offset: 0

Author

N. J. A. Sloane, Mar 21 2000

Keywords

• nonn
• easy
• nice

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

• 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).
• Index entries for linear recurrences with constant coefficients, signature (7,-18,20,-8).

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, A007466.

Programs

Magma

[2^(n-2)*(n^2-n+4)-1: n in [0..30]]; // Vincenzo Librandi, Oct 10 2011

Maple

A053545:=n->2^(n - 2)*(n^2 - n + 4) - 1; seq(A053545(n), n=0..30); # Wesley Ivan Hurt, Apr 01 2014

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 *)

PARI

a(n)=2^(n-2)*(n^2-n+4)-1 \\ Charles R Greathouse IV, Feb 19 2017

Formula

G.f.: x*(1-2x+2x^2)/((1-x)*(1-2x)^3).

a(n) = 2^(n-2)*(n^2-n+4)-1.

Partial sums of A007466. - J. M. Bergot, Jan 20 2013

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