cp's OEIS Frontend

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

%I A271771 #33 Oct 08 2024 14:09:35
%S A271771 1,5,18,53,140,347,826,1913,4344,9719,21494,47093,102388,221171,
%T A271771 475122,1015793,2162672,4587503,9699310,20447213,42991596,90177515,
%U A271771 188743658,394264553,822083560,1711276007,3556769766,7381975013,15300820964,31675383779
%N A271771 Maximum total Hamming distance between pairs of consecutive elements in any permutation of all 2^n binary words of length n.
%C A271771 Also the disorder number of the hypercube graph Q_n. - _Eric W. Weisstein_, Oct 08 2024
%H A271771 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 A271771 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 A271771 Sela Fried, <a href="https://arxiv.org/abs/2208.03788">On a conjecture of McNeil</a>, arXiv:2208.03788 [math.CO], 2023.
%H A271771 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 A271771 a(n) = n*2^n - 2^(n-1) - n + 1.
%F A271771 From _G. C. Greubel_, Apr 13 2013: (Start)
%F A271771 G.f.: x*(1 + 2*x)/(1-2*x)^2 - x^2/(1-x)^2.
%F A271771 E.g.f.: (2*x - 1/2)*exp(2*x) + (1 - x)*exp(x) - 1/2. (End)
%e A271771 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 A271771:=n->n*2^n - 2^(n-1) - n + 1: seq(A271771(n), n=1..50); # _Wesley Ivan Hurt_, Apr 18 2016
%t A271771 Table[n*2^n - 2^(n - 1) - n + 1, {n, 1, 30}] (* _Michael De Vlieger_, Apr 13 2016 *)
%o A271771 (C)  unsigned a(unsigned n) { return n*(1<<n) - (1<<(n-1)) - n + 1; }
%o A271771 (Magma) [n*2^n - 2^(n-1) - n + 1: n in [1..50]]; // _Wesley Ivan Hurt_, Apr 18 2016
%K A271771 nonn,easy
%O A271771 1,2
%A A271771 _Mark Jason Dominus_, Apr 13 2016