A356120 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 lexicographically ordered.

0, 0, 1, 0, 2, 3, 1, 0, 4, 6, 7, 5, 2, 3, 1, 0, 8, 12, 14, 15, 13, 10, 11, 9, 4, 6, 7, 5, 2, 3, 1, 0, 16, 24, 28, 30, 31, 29, 26, 27, 25, 20, 22, 23, 21, 18, 19, 17, 8, 12, 14, 15, 13, 10, 11, 9, 4, 6, 7, 5, 2, 3, 1, 0, 32, 48, 56, 60, 62, 63, 61, 58, 59, 57, 52, 54, 55, 53, 50, 51, 49, 40, 44, 46, 47, 45, 42

Offset: 0

Author

Valentin Bakoev, Jul 27 2022

Keywords

• nonn
• tabf

Comments

The sequence in the n-th row of the triangle is denoted by row(n). It contains the values in the range 0..2^n-1 corresponding to the binary vectors of length n. The integers in row (n), considered as characteristic vectors of the set B_n = {b_n, b_(n-1), ..., b_2, b_1}, whose elements are linearly ordered: b_n < b_(n-1) < ... < b_2 < b_1, define all subsets of B_n in lexicographic order. To obtain row(n) we reason inductively as follows. Obviously, row(0) = 0 = a(0) and corresponds to the empty set {}. Assume that the sequence row(n-1) = i_0, i_1, ..., i_(2^(n-1)-1) is obtained. It defines a lexicographic order of the subsets of B_(n-1) = {b_(n-1) , ..., b_2, b_1} - note that its elements linearly ordered. Then row (n) = i_0, 2^(n-1) + i_0, 2^(n-1) + i_1, ..., 2^(n-1) + i_(2^(n-1)-1), i_1, ..., i_(2^(n-1)-1) defines all subsets of B_n in lexicographic order. In other words, row(n) = 0, (row(n-1) + 2^(n-1)), (row(n-1) without the first term 0), i.e., row(n-1) is taken twice: first, all terms of row(n-1) are incremented by 2^(n-1) and second, the resulting sequence is inserted after the first term of row(n-1), which is always 0 and corresponds to {}.

Examples

			For n = 1, 2, 3, the sets B_n, their subsets (the column under B_n), binary characteristic words (column bin.) and corresponding integers (column dec.) are:
B_1 = {c}  bin.  dec. | B_2 = {b, c}  bin.   dec. | B_3 = {a, b, c}   bin.   dec.
      {}    0     0   |       {}       00     0   |       {}          000     0
      {c}   1     1   |       {b}      10     2   |       {a}         100     4
                      |       {b, c}   11     3   |       {a, b}      110     6
                      |          {c}   01     1   |       {a, b, c}   111     7
                                                  |       {a, c}      101     5
                                                  |          {b}      010     2
                                                  |          {b, c}   011     3
                                                  |             {c}   001     1
As seen, when B = {a, b, c}, its subsets {}, {a}, {a, b}, {a, b, c}, {a, c}, {b}, {b, c}, {c} are in lexicographic order, the corresponding binary words of length 3 are 000, 100, 110, 111, 101, 010, 011, 001, and so row(3) = 0, 4, 6, 7, 5, 2, 3, 1.
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, 3, 1;
  n=3:  0, 4, 6, 7, 5, 2, 3, 1;
  n=4:  0, 8, 12, 14, 15, 13, 10, 11, 9, 4, 6, 7, 5, 2, 3, 1;
  n=5:  0, 16, 24, 28, 30, 31, 29, 26, 27, 25, 20, 22, 23, 21, 18, 19, 17, 8, 12, 14, 15, 13, 10, 11, 9, 4, 6, 7, 5, 2, 3, 1,
  ...
		

References

• Donald E. Knuth, The Art of Computer Programming, Volume 4A, Section 7.2.1.3 Exercise 19 (Binomial tree traversed in post-order).

Links

• Valentin Bakoev, Table of n, a(n) for n = 0..1023
• Joerg Arndt, Matters Computational (The Fxtbook), section 1.26 "Binary words in lexicographic order for subsets", pp. 70-74.
• Joerg Arndt, Subset-lex: did we miss an order?, arXiv:1405.6503 [math.CO], 2014-2015.
• Valentin Bakoev, An Algorithm for Generating All Subsets in Lexicographic Order, ICAI 2022, pp. 271-275.

Crossrefs

Cf. A006516 (row sums), A000225 (main diagonal, the n-th term of row(n)).

row(n) without leading 0, when read in reverse order, gives the first 2^n-1 terms of A108918.

Starting with the n-th term of row(n), columns 0..4 are: A000004, A131577 without 0, A007283, A135092, A110286.

Programs

Mathematica

(* computing row(n) *)
n = 5;
Array[row, 2^n];
row[0] = 0; row[1] = 1;
len = 2;
For[i = 2, i <= n, i++,
  For[j = 1, j < len, j++, row[j + len] = row[j]];
  For[j = len, j > 0, j--, row[j] = row[j - 1] + len];
  len = len*2;
];

Formula

row(n) is defined as:

row(0) = 0;

row(n) = 0, (2^(n-1)+row(n-1)), (row(n-1)\{0}),

where (2^(n-1) + row(n-1)) means a subsequence obtained by adding 2^(n-1) to every term of row(n-1), and (row(n-1)\{0}) means a subsequence row(n-1) without its first term 0, for n = 0, 1, 2, ...).

Then a(n) is defined as:

a(2^m - 1) = 0, for m = 0, 1, 2, ..., and

a(2^m + k) = 2^(m-1) + a(2^(m-1) + k - 1), for k = 0, 1, ..., 2^(m-1) - 1, and

a(2^m + 2^(m-1) + k) = a(2^(m-1)+k), for k = 0, 1, ..., 2^(m-1) - 2.