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.

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

Author

Valentin Bakoev, Dec 27 2022

Keywords

• nonn
• tabf

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.

Examples

			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;
  ...
		

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.

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.

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).