|
| |
|
|
A294648
|
|
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.
|
|
15
|
|
|
|
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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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)):
|
|
|
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}]]];
|
|
|
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)
(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
|
A051459 gives the orders' number of the vectors of {0,1}^n in accordance with their weights.
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
