cp's OEIS Frontend

A351939 Irregular triangle read by rows: the n-th row contains the values 0..2^n-1 sorted first by Hamming weight and then by position in reflected Gray code.

%I A351939 #62 Oct 21 2022 14:24:09
%S A351939 0,0,1,0,1,2,3,0,1,2,4,3,6,5,7,0,1,2,4,8,3,6,5,12,10,9,7,13,14,11,15,
%T A351939 0,1,2,4,8,16,3,6,5,12,10,9,24,20,18,17,7,13,14,11,25,26,28,21,22,19,
%U A351939 15,27,30,29,23,31,0,1,2,4,8,16,32,3,6,5,12,10,9,24,20,18,17,48,40,36,34,33,7,13,14,11,25
%N A351939 Irregular triangle read by rows: the n-th row contains the values 0..2^n-1 sorted first by Hamming weight and then by position in reflected Gray code.
%C A351939 Values in the range 0..2^n-1 correspond to length n binary vectors. The Hamming weight is the number of 1 bits. Reflected Gray code is described in A003188 and A014550.
%C A351939 Rows can be subdivided into subsequences of vectors having the same Hamming weight. Within each subsequence, adjacent values will differ by 2 bits. For example, the subsequence of length 5 vectors with Hamming weight 2 is 00011, 00110, 00101, 01100, 01010, 01001, 11000, 10100, 10010, 10001 (in decimal 3, 6, 5, 12, 10, 9, 24, 20, 18, 17).
%C A351939 A revolving door algorithm can be used to enumerate values of the same weight in the required order. See Knuth ("Gray codes for combinations", p. 362) for additional information.
%D A351939 D. Knuth, The art of computer programming, Volume 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011.
%D A351939 F. Ruskey, Combinatorial Generation. Working Version (1j-CSC 425/520), 2003.
%H A351939 Valentin Bakoev, <a href="/A351939/b351939.txt">Table of n, a(n) for n = 0..65535</a>
%H A351939 Valentin Bakoev, <a href="https://doi.org/10.1142/S179383092150021X">Some problems and algorithms related to the weight order relation on the n-dimensional Boolean cube</a>, Discrete Mathematics, Algorithms and Applications, Vol. 13 No 3, 2150021 (2021); <a href="https://arxiv.org/abs/1811.04421">arXiv preprint</a>, arXiv:1811.04421 [cs.DM], 2018-2020.
%H A351939 Valentin Bakoev, <a href="https://doi.org/10.1007/978-3-031-19685-0_4">Ordering the Boolean Cube Vectors by Their Weights and with Minimal Change</a>, Int'l Conf. Algebraic Informatics (CAI 2022) Lecture Notes Comp. Sci. (LNCS) Vol. 13706, 43-54.
%H A351939 Sage Reference Manual, <a href="https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/gray_codes.html">Gray codes</a>
%F A351939 The n-th row is the concatenation of the subsequences g(n, 0), ..., g(n, n), where the subsequences are defined as follows:
%F A351939   g(n, 0) = (0),
%F A351939   g(n, n) = (2^n - 1),
%F A351939   g(n, k) = g(n-1, k) concatenate (g^r(n-1, k-1) + 2^(n-1)) for 0 < k < n.
%F A351939 In the above, g^r(n-1, k-1) + 2^(n-1) means the 2^(n-1) is added to each member of the subsequence g(n-1, k-1) in reversed order.
%e A351939 Triangle T(n,k) begins:
%e A351939 n=0: 0;
%e A351939 n=1: 0, 1;
%e A351939 n=2: 0, 1, 2, 3;
%e A351939 n=3: 0, 1, 2, 4, 3, 6, 5, 7;
%e A351939 n=4: 0, 1, 2, 4, 8, 3, 6, 5, 12, 10, 9, 7, 13, 14, 11, 15;
%e A351939 n=5: 0, 1, 2, 4, 8, 16, 3, 6, 5, 12, 10, 9, 24, 20, 18, 17, 7, 13, 14, 11, 25, 26, 28, 21, 22, 19, 15, 27, 30, 29, 23, 31;
%e A351939 ...
%e A351939 For row n = 3, the binary words of length 3 in reflected Gray code order are 000, 001, 011, 010, 110, 111, 101, 100. Arranging these by Hamming weight but otherwise preserving the order gives 000, 001, 010, 100, 011, 110, 101, 111. As decimal numbers these are 0, 1, 2, 4, 3, 6, 5, 7, which is row 3.
%p A351939 b:= proc(n) b(n):= `if`(n<2, n, Bits[Xor](n, b(iquo(n, 2)))) end:
%p A351939 h:= proc(n) h(n):= add(i, i=Bits[Split](n)) end:
%p A351939 T:= n-> sort([$0..2^n-1], (x,y)-> h(x)<h(y) or h(x)=h(y) and b(x)<b(y))[]:
%p A351939 seq(T(n), n=0..6);  # _Alois P. Heinz_, Mar 01 2022
%t A351939 b[n_] := If[n < 2, n, BitXor[n, b[Quotient[n, 2]]]];
%t A351939 h[n_] := DigitCount[n, 2, 1];
%t A351939 T[n_] := SortBy[{h, b}][Range[0, 2^n - 1]];
%t A351939 Table[T[n], {n, 0, 6}] // Flatten (* _Jean-François Alcover_, Oct 21 2022, after _Alois P. Heinz_ *)
%o A351939 (PARI) row(n)=vecsort(vector(2^n, i, i--; bitxor(i, i>>1)), (x,y) -> cmp(hammingweight(x), hammingweight(y)))
%o A351939 { for(n=0, 5, print(row(n))) } \\ _Andrew Howroyd_, Feb 28 2022
%Y A351939 Row sums are A006516.
%Y A351939 Right border gives A000225.
%Y A351939 Left border gives A000004.
%Y A351939 T(n,n) gives A131577.
%Y A351939 Cf. A000120 (Hamming weight), A003188, A014550 (reflected Gray code), A294648 (weight-lexicographic order).
%K A351939 nonn,tabf
%O A351939 0,6
%A A351939 _Valentin Bakoev_, Feb 26 2022