A356120 - OEIS

%I #30 Jan 08 2023 16:29:42

%S 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,

%T 0,16,24,28,30,31,29,26,27,25,20,22,23,21,18,19,17,8,12,14,15,13,10,

%U 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

%N 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.

%C 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 {}.

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

%H Valentin Bakoev, <a href="/A356120/b356120.txt">Table of n, a(n) for n = 0..1023</a>

%H Joerg Arndt, <a href="https://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 1.26 "Binary words in lexicographic order for subsets", pp. 70-74.

%H Joerg Arndt, <a href="https://arxiv.org/abs/1405.6503">Subset-lex: did we miss an order?</a>, arXiv:1405.6503 [math.CO], 2014-2015.

%H 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 row(n) is defined as:

%F row(0) = 0;

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

%F 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, ...).

%F Then a(n) is defined as:

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

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

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

%e 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:

%e B_1 = {c}  bin.  dec. | B_2 = {b, c}  bin.   dec. | B_3 = {a, b, c}   bin.   dec.

%e       {}    0     0   |       {}       00     0   |       {}          000     0

%e       {c}   1     1   |       {b}      10     2   |       {a}         100     4

%e                       |       {b, c}   11     3   |       {a, b}      110     6

%e                       |          {c}   01     1   |       {a, b, c}   111     7

%e                                                   |       {a, c}      101     5

%e                                                   |          {b}      010     2

%e                                                   |          {b, c}   011     3

%e                                                   |             {c}   001     1

%e 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.

%e Triangle T(n,k) begins:

%e       k=0  1  2  3  4  5  6  7 ...

%e   n=0:  0;

%e   n=1:  0, 1;

%e   n=2:  0, 2, 3, 1;

%e   n=3:  0, 4, 6, 7, 5, 2, 3, 1;

%e   n=4:  0, 8, 12, 14, 15, 13, 10, 11, 9, 4, 6, 7, 5, 2, 3, 1;

%e   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,

%e   ...

%t (* computing row(n) *)

%t n = 5;

%t Array[row, 2^n];

%t row[0] = 0; row[1] = 1;

%t len = 2;

%t For[i = 2, i <= n, i++,

%t   For[j = 1, j < len, j++, row[j + len] = row[j]];

%t   For[j = len, j > 0, j--, row[j] = row[j - 1] + len];

%t   len = len*2;

%t ];

%o (C++) // To generate a(0), a(1), ..., a(2^m-1) of A356120

%o void a356120 (int m) {

%o    a[0] = 0;

%o    uint clen = 2; // length of the current row (= 2^i)

%o    uint plen = 1; // length of the previous row (= 2^(i-1))

%o    for (int i = 1; i <= m; i++) {

%o       a[clen-1] = 0;

%o       for (int k = 0; k < plen; k++)

%o          a[clen + k] = plen + a[plen + k - 1];

%o       for (int k = 0; k < plen-1; k++)

%o          a[clen + plen + k] = a[plen + k];

%o       plen = clen;

%o       clen *= 2;

%o    }

%o }

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

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

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

%K nonn,tabf

%O 0,5

%A _Valentin Bakoev_, Jul 27 2022