cp's OEIS Frontend

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.

%I A359336 #35 Mar 01 2023 14:51:49
%S A359336 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,
%T A359336 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,
%U A359336 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
%N 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.
%C A359336 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.
%C A359336 Equivalently, the sequence in row(n) defines all (n,k) combinations over a linearly ordered set in lexicographic order, for k = 0, 1, ..., n.
%C A359336 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.
%C A359336 Following the formula for row(n), we get:
%C A359336 T(n,0) = 0;
%C A359336 T(n, 2^n-1) = 2^n-1;
%C A359336 T(n,n) = 1, for n >= 1.
%C A359336 T(n,k) = 2^(n-k) for 1 <= k <= n.
%C A359336 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.
%H A359336 Valentin Bakoev, <a href="/A359336/b359336.txt">Rows n = 0..10, flattened</a>
%H A359336 Valentin Bakoev, <a href="https://doi.org/10.1142/S179383092150021X">Some problems and algorithms related to the weight order relation on the n-dimensional Boolean cube</a>, Discrete Mathematics, Algorithms and Applications, Vol. 13 No 3, 2150021 (2021); <a href="https://arxiv.org/abs/1811.04421">arXiv preprint</a>, arXiv:1811.04421 [cs.DM], 2018-2020.
%H A359336 Valentin Bakoev, <a href="https://doi.org/10.1109/ICAI55857.2022.9959993">An Algorithm for Generating All Subsets in Lexicographic Order</a>, ICAI 2022, pp. 271-275.
%F A359336 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:
%F A359336 r(n, 0) = (0),
%F A359336 r(n, n) = (2^n - 1),
%F A359336 r(n, k) = (r(n-1, k-1) + 2^(n-1)) concatenate r(n-1, k), for 0 < k < n.
%F A359336 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).
%e A359336 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.
%e A359336 dec., bin., B_3 = {a, b, c}
%e A359336 ---------------------------
%e A359336  0    000        {}
%e A359336  4    100        {a}
%e A359336  2    010        {b}
%e A359336  1    001        {c}
%e A359336  6    110        {a, b}
%e A359336  5    101        {a, c}
%e A359336  3    011        {b, c}
%e A359336  7    111        {a, b, c}
%e A359336 As seen, the corresponding subsets of equal size are ordered lexicographically.
%e A359336 Triangle T(n,k) begins:
%e A359336     k = 0   1   2   3   4   5   6   7 ...
%e A359336   n=0:  0;
%e A359336   n=1:  0,  1;
%e A359336   n=2:  0,  2,  1,  3;
%e A359336   n=3:  0,  4,  2,  1,  6,  5,  3,  7;
%e A359336   n=4:  0,  8,  4,  2,  1, 12, 10,  9,  6,  5,  3, 14, 13, 11,  7, 15,
%e A359336   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;
%e A359336   ...
%Y A359336 Cf. A000004 (column k=0), A000225 (right border), A000012 (main diagonal), A006516 (row sums).
%Y A359336 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).
%Y A359336 Cf. A356028.
%K A359336 nonn,tabf
%O A359336 0,5
%A A359336 _Valentin Bakoev_, Dec 27 2022