Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%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