OFFSET
1,5
COMMENTS
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.
LINKS
Michael De Vlieger, Table of n, a(n) for n = 1..10000
Valentin Bakoev, Some problems and algorithms related to the weight order relation on the n-dimensional Boolean cube, Discrete Mathematics, Algorithms and Applications, Vol. 13 No 3, 2150021 (2021); arXiv preprint, arXiv:1811.04421 [cs.DM], 2018-2020.
Valentin Bakoev, Fast Computing the Algebraic Degree of Boolean Functions, arXiv:1905.08649 [cs.DM], 2019.
FORMULA
For n=1, 2, 3, ..., L(n) is defined by the recurrence:
if n=1, L(1)= 0, 1;
else L(n)= l(n, 0), l(n, 1), ..., l(n, k), ..., l(n, n), where the subsequences are defined as follows:
l(n, k)= 0, if k=0, else
l(n, k)= 2^n - 1, if k=n, else
l(n, k)= l(n-1, k), l(n-1, k-1) + 2^{n-1}, for 0 < k < n.
Comments:
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).
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.
3) The inductive formula, corresponding to the recurrence, is much more useful for implementations.
EXAMPLE
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.
The triangle starts:
n=1: 0, 1;
n=2: 0, 1, 2, 3;
n=3: 0, 1, 2, 4, 3, 5, 6, 7;
n=4: 0, 1, 2, 4, 8, 3, 5, 6, 9, 10, 12, 7, 11, 13, 14, 15;
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;
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;
MAPLE
with(ListTools): conc := (a, b, c) -> Flatten([op(a), [seq(op(j)+c, j in b)]], 1):
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:
L := n -> `if`(n=1, [0, 1], Flatten([seq(rec(n, k), k=0..n)], 1)):
Flatten([seq(L(n), n = 1..6)], 1); # Peter Luschny, Nov 06 2017
MATHEMATICA
conc[a_List, b_List, c_] := Join[a, b + c];
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)]]];
L[n_] := If[n == 1, {0, 1}, Flatten[Table[rec[n, k], {k, 0, n}]]];
Array[L, 6] // Flatten (* Jean-François Alcover, Jul 26 2018, after Peter Luschny *)
PROG
(Python)
from itertools import product
def sortby(x): return (len(x), x.count('1'), x)
def agen(maxbindigs):
for i in range(1, maxbindigs+1):
for t in sorted([p for p in product("01", repeat=i)], key=sortby):
yield int("".join(t), 2)
print([an for an in agen(6)]) # Michael S. Branicky, Aug 13 2021
(PARI) cmph(x, y) = my(d=hammingweight(x)-hammingweight(y)); if (d, d, x-y);
row(n) = my(v=[0..2^n-1]); vecsort(v, cmph); \\ Michel Marcus, Sep 16 2023
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Valentin Bakoev, Nov 06 2017
STATUS
approved