A271771 - OEIS

%I #33 Oct 08 2024 14:09:35

%S 1,5,18,53,140,347,826,1913,4344,9719,21494,47093,102388,221171,

%T 475122,1015793,2162672,4587503,9699310,20447213,42991596,90177515,

%U 188743658,394264553,822083560,1711276007,3556769766,7381975013,15300820964,31675383779

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

%C Also the disorder number of the hypercube graph Q_n. - _Eric W. Weisstein_, Oct 08 2024

%H Math StackExchange, <a href="http://math.stackexchange.com/questions/315544/25554">“Anti-Gray codes” that maximize the number of bits that change at each step</a>

%H Mehmet Kurt, Can Atilgan, and Murat Ersen Berberler <a href="https://citeseerx.ist.psu.edu/pdf/e9b1fb4d44927dc77836f382ea3410ef329c64f7">A Dynamic Programming Approach for Generating N-ary Reflected Gray Code List</a>, 2013, see section 4 on page 4.

%H Sela Fried, <a href="https://arxiv.org/abs/2208.03788">On a conjecture of McNeil</a>, arXiv:2208.03788 [math.CO], 2023.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DisorderNumber.html">Disorder Number</a>.Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HypercubeGraph.html">Hypercube Graph</a>.

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

%F From _G. C. Greubel_, Apr 13 2013: (Start)

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

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

%e 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.

%p A271771:=n->n*2^n - 2^(n-1) - n + 1: seq(A271771(n), n=1..50); # _Wesley Ivan Hurt_, Apr 18 2016

%t Table[n*2^n - 2^(n - 1) - n + 1, {n, 1, 30}] (* _Michael De Vlieger_, Apr 13 2016 *)

%o (C)  unsigned a(unsigned n) { return n*(1<<n) - (1<<(n-1)) - n + 1; }

%o (Magma) [n*2^n - 2^(n-1) - n + 1: n in [1..50]]; // _Wesley Ivan Hurt_, Apr 18 2016

%K nonn,easy

%O 1,2

%A _Mark Jason Dominus_, Apr 13 2016