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

Offset: 1

Author

Ross Drewe, Aug 03 2025

Keywords

• nonn
• more

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.

Examples

			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.
		

Crossrefs

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

Programs

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

Formula

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

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

Extensions

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