login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

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(0)=0, a(1)=1, a(2)=5, a(3)=19, a(n)=7*a(n-1)-18*a(n-2)+20*a(n-3)-8*a(n-4). - Harvey P. Dale, Apr 03 2013

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

PROG

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

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

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 * A049612 A211842 A304134

Adjacent sequences:  A053542 A053543 A053544 * A053546 A053547 A053548

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane, Mar 21 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 17 18:47 EDT 2019. Contains 325109 sequences. (Running on oeis4.)