OFFSET
0,5
COMMENTS
The n-th row of the table is denoted by row(n) and contains a permutation of the integers from the interval [0, 2^n-1] which defines an ordering of all binary vectors of length n. Let the elements of the set B_n = {b_n, b_(n-1), ..., b_2, b_1} be linearly ordered: b_n < b_(n-1) < ... < b_2 < b_1. When we consider the binary vectors defined by row(n) as characteristic vectors, they define all subsets of B_n, sorted first by their cardinalities and then lexicographically. The sequence in row(n) is partitioned into n+1 subsequences of integers whose binary vectors have the same (Hamming) weight.
Equivalently, the sequence in row(n) defines all (n,k) combinations over a linearly ordered set in lexicographic order, for k = 0, 1, ..., n.
Like A294648 and A351939, A359336 represents one of the numerous weight orderings of the vectors of the n-dimensional Boolean cube (or the subsets of a set of n-elements sorted by their size) - see A051459.
Following the formula for row(n), we get:
T(n,0) = 0;
T(n, 2^n-1) = 2^n-1;
T(n,n) = 1, for n >= 1.
T(n,k) = 2^(n-k) for 1 <= k <= n.
Thus the regular triangle T(n,k), for n = 1, 2, 3, ... and for 1 <= k <= n consists of powers of 2 (A000079): in ascending order by columns and in descending order by rows.
LINKS
Valentin Bakoev, Rows n = 0..10, flattened
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, An Algorithm for Generating All Subsets in Lexicographic Order, ICAI 2022, pp. 271-275.
FORMULA
For n = 1, 2, 3, ..., row(n) is a concatenation of the subsequences r(n, 0), r(n, 1), ..., r(n, n) defined by the recurrence:
r(n, 0) = (0),
r(n, n) = (2^n - 1),
r(n, k) = (r(n-1, k-1) + 2^(n-1)) concatenate r(n-1, k), for 0 < k < n.
In the above, r(n-1, k-1) + 2^(n-1) means the 2^(n-1) is added to each member of the subsequence r(n-1, k-1).
EXAMPLE
In the following table, the members of row(3) are given in column dec., the corresponding characteristic vectors are in column bin., and the corresponding subsets of B_3 are listed under B_3.
dec., bin., B_3 = {a, b, c}
---------------------------
0 000 {}
4 100 {a}
2 010 {b}
1 001 {c}
6 110 {a, b}
5 101 {a, c}
3 011 {b, c}
7 111 {a, b, c}
As seen, the corresponding subsets of equal size are ordered lexicographically.
Triangle T(n,k) begins:
k = 0 1 2 3 4 5 6 7 ...
n=0: 0;
n=1: 0, 1;
n=2: 0, 2, 1, 3;
n=3: 0, 4, 2, 1, 6, 5, 3, 7;
n=4: 0, 8, 4, 2, 1, 12, 10, 9, 6, 5, 3, 14, 13, 11, 7, 15,
n=5: 0, 16, 8, 4, 2, 1, 24, 20, 18, 17, 12, 10, 9, 6, 5, 3, 28, 26, 25, 22, 21, 19, 14, 13, 11, 7, 30, 29, 27, 23, 15, 31;
...
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Valentin Bakoev, Dec 27 2022
STATUS
approved