%I #36 Feb 17 2022 01:07:59
%S 0,1,5,19,63,191,543,1471,3839,9727,24063,58367,139263,327679,761855,
%T 1753087,3997695,9043967,20316159,45350911,100663295,222298111,
%U 488636415,1069547519,2332033023,5066719231,10972299263,23689428991,51002736639,109521666047,234612588543,501437431807
%N Comparisons needed for Batcher's sorting algorithm applied to 2^n items.
%C 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.
%C Binomial transform of A005893: (1, 4, 10, 20, 34, 52, 74, ...) = (1, 5, 19, 63, 191, ...). - _Gary W. Adamson_, Apr 28 2008
%C 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
%H Vincenzo Librandi, <a href="/A053545/b053545.txt">Table of n, a(n) for n = 0..3000</a>
%H I. Wegener, <a href="https://web.archive.org/web/20100630083317/http://ls2-www.cs.uni-dortmund.de/monographs/bluebook/index.shtml.en">The Complexity of Boolean Functions</a>, Wiley, 1987, see p. 151, (2.7).
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (7,-18,20,-8).
%F G.f.: x*(1-2x+2x^2)/((1-x)*(1-2x)^3).
%F a(n) = 2^(n-2)*(n^2-n+4)-1.
%F Partial sums of A007466. - _J. M. Bergot_, Jan 20 2013
%F 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
%p A053545:=n->2^(n - 2)*(n^2 - n + 4) - 1; seq(A053545(n), n=0..30); # _Wesley Ivan Hurt_, Apr 01 2014
%t 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 *)
%o (Magma) [2^(n-2)*(n^2-n+4)-1: n in [0..30]]; // _Vincenzo Librandi_, Oct 10 2011
%o (PARI) a(n)=2^(n-2)*(n^2-n+4)-1 \\ _Charles R Greathouse IV_, Feb 19 2017
%Y 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).
%Y Cf. A005893, A007466.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_, Mar 21 2000