OFFSET
1,2
COMMENTS
Also the disorder number of the hypercube graph Q_n. - Eric W. Weisstein, Oct 08 2024
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.
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
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
KEYWORD
nonn,easy
AUTHOR
Mark Jason Dominus, Apr 13 2016
STATUS
approved