login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A359336
Irregular triangle read by rows: the n-th row lists the values 0..2^n-1 representing all subsets of a set of n elements. When its elements are linearly ordered, the subsets are sorted first by their size and then lexicographically.
1
0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 1, 6, 5, 3, 7, 0, 8, 4, 2, 1, 12, 10, 9, 6, 5, 3, 14, 13, 11, 7, 15, 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, 0, 32, 16, 8, 4, 2, 1, 48, 40, 36, 34, 33, 24, 20, 18, 17, 12, 10, 9, 6, 5, 3, 56, 52, 50, 49
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
Cf. A000004 (column k=0), A000225 (right border), A000012 (main diagonal), A006516 (row sums).
Cf. A294648 (weight-lexicographic order of the binary vectors), A351939 (the values 0..2^n-1 sorted first by Hamming weight and then by position in reflected Gray code).
Cf. A356028.
Sequence in context: A195084 A081171 A334594 * A062778 A363620 A363624
KEYWORD
nonn,tabf
AUTHOR
Valentin Bakoev, Dec 27 2022
STATUS
approved