A271771 Maximum total Hamming distance between pairs of consecutive elements in any permutation of all 2^n binary words of length n.

1, 5, 18, 53, 140, 347, 826, 1913, 4344, 9719, 21494, 47093, 102388, 221171, 475122, 1015793, 2162672, 4587503, 9699310, 20447213, 42991596, 90177515, 188743658, 394264553, 822083560, 1711276007, 3556769766, 7381975013, 15300820964, 31675383779

Offset

1,2

Links

Table of n, a(n) for n=1..30.

Math StackExchange, “Anti-Gray codes” that maximize the number of bits that change at each step

Mehmet Kurt, Can Atilgan, and Murat Ersen Berberler A Dynamic Programming Approach for Generating N-ary Reflected Gray Code List, 2013, see section 4 on page 4.

Formula

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

From G. C. Greubel, Apr 13 2013: (Start)

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

E.g.f.: (2*x - 1/2)*exp(2*x) + (1 - x)*exp(x) - 1/2. (End)

Example

Example: for n=3 the sequence 000 111 001 110 011 100 010 101 has total hamming distance 3+2+3+2+3+2+3 = 18.

Maple

A271771:=n->n*2^n - 2^(n-1) - n + 1: seq(A271771(n), n=1..50); # Wesley Ivan Hurt, Apr 18 2016

Mathematica

Table[n*2^n - 2^(n - 1) - n + 1, {n, 1, 30}] (* Michael De Vlieger, Apr 13 2016 *)

Prog

(C)  unsigned a(unsigned n) { return n*(1<<n) - (1<<(n-1)) - n + 1; }
(Magma) [n*2^n - 2^(n-1) - n + 1: n in [1..50]]; // Wesley Ivan Hurt, Apr 18 2016

Crossrefs

Sequence in context: A056782 A178684 A353689 * A270990 A272558 A081492

Adjacent sequences: A271768 A271769 A271770 * A271772 A271773 A271774

Keyword

nonn,easy

Author

Mark Jason Dominus, Apr 13 2016

Status

approved