|
| |
|
|
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.
|
|
1
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
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 {}.
|
|
|
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
|
|
|
|
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.
|
|
|
EXAMPLE
|
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,
...
|
|
|
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;
];
|
|
|
PROG
|
(C++) // To generate a(0), a(1), ..., a(2^m-1) of A356120
void a356120 (int m) {
a[0] = 0;
uint clen = 2; // length of the current row (= 2^i)
uint plen = 1; // length of the previous row (= 2^(i-1))
for (int i = 1; i <= m; i++) {
a[clen-1] = 0;
for (int k = 0; k < plen; k++)
a[clen + k] = plen + a[plen + k - 1];
for (int k = 0; k < plen-1; k++)
a[clen + plen + k] = a[plen + k];
plen = clen;
clen *= 2;
}
}
|
|
|
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.
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
