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
Examples
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.
Links
- 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.
- 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.
Programs
-
C
unsigned a(unsigned n) { return n*(1< -
Magma
[n*2^n - 2^(n-1) - n + 1: n in [1..50]]; // Wesley Ivan Hurt, Apr 18 2016
-
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 *)
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)
Comments