A385185 Number of permutations of 0..n-1 which are binary Gray codes.

1, 2, 2, 8, 4, 16, 24, 144, 36, 164, 192, 1168, 976, 5688, 10656, 91392, 11424, 67032, 61840, 403568, 258956, 1589080, 2520324, 22646880, 10898976, 67039504, 93326800, 819193248, 924489888, 7399407552, 16309883520, 187499658240, 11718728640, 96818811456, 71979698880

Offset

1,2

Comments

In a binary Gray code, the binary expansions of any two consecutive terms differ at a single bit position.

When n is odd, the binary weights of n and the first term in the permutation must have opposite parity, since otherwise it's not possible to step through all of 0,...,n-1.

Links

Table of n, a(n) for n=1..35.

Formula

a(2^n) = A091299(n).

a(2^n+1) = a(2^n)/2^(n-1) for n > 0. - Andrew Howroyd, Aug 04 2025

Example

For n=5, the a(5) = 4 possible permutations which are Gray codes are
  1 3 2 0 4
  2 3 1 0 4
  4 0 1 3 2
  4 0 2 3 1
For n=8, a(8) = 144 includes 0 1 3 2 6 4 5 7 which is lexicographically smallest, and also includes the binary reflected Graycode 0 1 3 2 6 7 5 4.

Prog

(MATLAB)
function N = Gcode(L); H = hmap; N = 0; unused = uint8([0: L-1]); for i = 1:length(unused); g = unused(i); u = unused; u(i) = []; gray(g, u); end
function gray(g, u); curidx = g(end) + 1; d = H(curidx, :); if isscalar(u); if d(u+1); N = N + 1; end; else for j = 1: length(u); r = u(j); if d(r+1); nextg = [g r]; nextu = u; nextu(j) = []; gray(nextg, nextu); end; end; end; end
function map = hmap; map = false(L, L); S = uint8([0:L-1]); [X, Y] = meshgrid(S); X = X(:); Y = Y(:);
xb = de2bi(X); yb = de2bi(Y); for k = 1:L^2; v = sum(bitxor(xb(k, :), yb(k, :))); if v == 1; map(k) = true; end; end; end; end
(PARI)
f(i, r, s) = if(s, foreach(v[i], x, if(bitand(r, 1<<x), f(x, bitxor(r, 1<<x), s-1))), c++);
g(i, j, r, s) = if(s, my(t); foreach(v[i], x, if(bitand(r, 1<<x), t=bitxor(r, 1<<x); f(x, t, s-1); foreach(v[j], y, if(bitand(t, 1<<y), g(x, y, bitxor(t, 1<<y), s-2))))); foreach(v[j], y, if(bitand(r, 1<<y), f(y, bitxor(r, 1<<y), s-1))), c++);
a(n) = if(n>1, c=0; v=vector(n, i, List([])); my(t); for(i=2, n, for(j=1, i-1, t=bitxor(i-1, j-1); if(!bitand(t, t-1), listput(v[i], j); listput(v[j], i)))); t=2^(n+1)-4; f(1, t, n-1); for(i=2, #v[1], for(j=1, i-1, g(v[1][i], v[1][j], t-2^v[1][i]-2^v[1][j], n-3))); 2*c, 1); \\ Jinyuan Wang, Sep 07 2025

Crossrefs

Cf. A091299, A350784 (when beginning with 0).

Sequence in context: A003612 A337944 A103839 * A135727 A320423 A274449

Adjacent sequences: A385182 A385183 A385184 * A385187 A385188 A385189

Keyword

nonn

Author

Ross Drewe, Aug 03 2025

Extensions

a(27)-a(33) from Andrew Howroyd, Aug 04 2025

a(34)-a(35) from Jinyuan Wang, Sep 06 2025

Status

approved