%I #61 Sep 16 2023 12:23:16
%S 0,1,0,1,2,3,0,1,2,4,3,5,6,7,0,1,2,4,8,3,5,6,9,10,12,7,11,13,14,15,0,
%T 1,2,4,8,16,3,5,6,9,10,12,17,18,20,24,7,11,13,14,19,21,22,25,26,28,15,
%U 23,27,29,30,31,0,1,2,4,8,16,32,3,5,6,9,10,12,17,18,20,24,33,34,36,40,48,7,11,13,14,19,21
%N Irregular triangle read by rows, representing a family of sequences L(n), for n=1, 2, 3, ... The sequence L(n) (i.e., the n-th row) is the ordinance of vectors of the n-dimensional Boolean cube (hypercube) {0,1}^n in accordance with their (Hamming) weights, where the lexicographic order is chosen as a second criterion for an ordinance the vectors of equal weights.
%C The sequences represent the ordinance of vectors of the n-dimensional Boolean cube (hypercube) {0,1}^n in accordance with their (Hamming) weights. The lexicographic order is chosen as a second criterion for the ordinance of the vectors of equal weights. We refer to this order as a Weight-Lexicographic Order (WLO). The WLO is represented by the (serial) numbers of the vectors, instead of the vectors itself. It is well known that if the vectors of {0,1}^n are in lexicographic (standard) order, their numbers form the sequence of natural numbers 0, 1, 2, ..., 2^n-1. So, the WLO means a permutation of the numbers 0, 1, 2, ..., 2^n-1, such that the corresponding vectors are in WLO. This sequence (permutation) is denoted by L(n). It consists of (n+1) subsequences, corresponding to the layers of the Boolean cube.
%H Michael De Vlieger, <a href="/A294648/b294648.txt">Table of n, a(n) for n = 1..10000</a>
%H 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 Valentin Bakoev, <a href="https://arxiv.org/abs/1905.08649">Fast Computing the Algebraic Degree of Boolean Functions</a>, arXiv:1905.08649 [cs.DM], 2019.
%F For n=1, 2, 3, ..., L(n) is defined by the recurrence:
%F if n=1, L(1)= 0, 1;
%F else L(n)= l(n, 0), l(n, 1), ..., l(n, k), ..., l(n, n), where the subsequences are defined as follows:
%F l(n, k)= 0, if k=0, else
%F l(n, k)= 2^n - 1, if k=n, else
%F l(n, k)= l(n-1, k), l(n-1, k-1) + 2^{n-1}, for 0 < k < n.
%F Comments:
%F 1) l(n, k)= l(n-1, k}, l(n-1, k-1) + 2^{n-1} means that l(n, k) is a concatenation of two subsequences: l(n-1, k) and l(n-1, k-1) + 2^{n-1}. The second one is obtained after addition of the number 2^{n-1} to each member of l(n-1,k-1).
%F 2) The computing of the members of L(n) resembles the computing (and filling in) the binomial coefficients in Pascal's triangle. The binomial coefficients determine the lengths of the subsequences l(n, k), 0 <= k <= n, in L(n). Thus the beginning of each subsequence can be computed easily.
%F 3) The inductive formula, corresponding to the recurrence, is much more useful for implementations.
%e The lexicographic order of {0,1}^3 is: (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1), and the corresponding sequence of (serial) numbers is: 0, 1, 2, ..., 7. The WLO of these vectors is given by the sequence L(3)= 0, 1, 2, 4, 3, 5, 6, 7.
%e The triangle starts:
%e n=1: 0, 1;
%e n=2: 0, 1, 2, 3;
%e n=3: 0, 1, 2, 4, 3, 5, 6, 7;
%e n=4: 0, 1, 2, 4, 8, 3, 5, 6, 9, 10, 12, 7, 11, 13, 14, 15;
%e n=5: 0, 1, 2, 4, 8, 16, 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 15, 23, 27, 29, 30, 31;
%e n=6: 0, 1, 2, 4, 8, 16, 32, 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 31, 47, 55, 59, 61, 62, 63;
%p with(ListTools): conc := (a,b,c) -> Flatten([op(a),[seq(op(j)+c, j in b)]], 1):
%p rec := proc(n,k) option remember; `if`(k=0, [0], `if`(k=n, [2^n-1], conc(rec(n-1,k), rec(n-1,k-1), 2^(n-1)))) end:
%p L := n -> `if`(n=1, [0,1], Flatten([seq(rec(n,k),k=0..n)], 1)):
%p Flatten([seq(L(n), n = 1..6)], 1); # _Peter Luschny_, Nov 06 2017
%t conc[a_List, b_List, c_] := Join[a, b + c];
%t rec[n_, k_] := rec[n, k] = If[k == 0, {0}, If[k == n, {2^n - 1}, conc[rec[n - 1, k], rec[n - 1, k - 1], 2^(n - 1)]]];
%t L[n_] := If[n == 1, {0, 1}, Flatten[Table[rec[n, k], {k, 0, n}]]];
%t Array[L, 6] // Flatten (* _Jean-François Alcover_, Jul 26 2018, after _Peter Luschny_ *)
%o (Python)
%o from itertools import product
%o def sortby(x): return (len(x), x.count('1'), x)
%o def agen(maxbindigs):
%o for i in range(1, maxbindigs+1):
%o for t in sorted([p for p in product("01", repeat=i)], key=sortby):
%o yield int("".join(t), 2)
%o print([an for an in agen(6)]) # _Michael S. Branicky_, Aug 13 2021
%o (PARI) cmph(x, y) = my(d=hammingweight(x)-hammingweight(y)); if (d, d, x-y);
%o row(n) = my(v=[0..2^n-1]); vecsort(v, cmph); \\ _Michel Marcus_, Sep 16 2023
%Y A051459 gives the orders' number of the vectors of {0,1}^n in accordance with their weights.
%Y Cf. A091444 (as bits), A187769, A007318.
%K nonn,tabf
%O 1,5
%A _Valentin Bakoev_, Nov 06 2017