login
A271771
Maximum total Hamming distance between pairs of consecutive elements in any permutation of all 2^n binary words of length n.
2
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
COMMENTS
Also the disorder number of the hypercube graph Q_n. - Eric W. Weisstein, Oct 08 2024
LINKS
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.
Sela Fried, On a conjecture of McNeil, arXiv:2208.03788 [math.CO], 2023.
Eric Weisstein's World of Mathematics, Disorder Number.Eric Weisstein's World of Mathematics, Hypercube Graph.
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
KEYWORD
nonn,easy
AUTHOR
Mark Jason Dominus, Apr 13 2016
STATUS
approved