|
| |
|
|
A362160
|
|
Irregular triangle read by rows: The n-th row contains 2^n integers corresponding to the words of the n-bit Gray code with the most significant bits changing fastest.
|
|
2
|
|
|
|
0, 0, 1, 0, 2, 3, 1, 0, 4, 6, 2, 3, 7, 5, 1, 0, 8, 12, 4, 6, 14, 10, 2, 3, 11, 15, 7, 5, 13, 9, 1, 0, 16, 24, 8, 12, 28, 20, 4, 6, 22, 30, 14, 10, 26, 18, 2, 3, 19, 27, 11, 15, 31, 23, 7, 5, 21, 29, 13, 9, 25, 17, 1, 0, 32, 48, 16, 24, 56, 40, 8, 12, 44, 60, 28
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
The n-th row of the triangle is defined recursively as row(0) = 0 which corresponds to the empty word, and row(n) = row(n-1)0, row^r(n-1)1, for n > 0. Here row(n-1)0 is the sequence of words of the (n-1)-bit Gray code of this type suffixed with 0, and row^r(n-1)1 means the sequence of reflected words (i.e., words are taken in reverse order) of the (n-1)-bit Gray code of this type and then each word is suffixed with 1.
Another way to obtain row(n) is by applying the transition sequence A001511(n), which indicates which bit to flip in the current word to get the next word - see the FORMULA section.
If we reverse the internal order of bits in each word of row(n), we obtain the binary reflected n-bit Gray code (see A003188) and vice versa.
|
|
|
REFERENCES
|
W. Lipski Jr, Combinatorics for programmers, Mir, Moscow, 1988, (in Russsian), p. 31, Algorithm 1.13.
F. Ruskey, Combinatorial Generation. Working Version (1j-CSC 425/520), 2003, pp. 120-121.
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = 2*T(n-1,k) for 0 <= k < 2^(n-1), and
T(n,2^(n-1)+k) = 2*T(n-1,2^(n-1)-k-1) + 1 = T(n,2^(n-1)-k-1) + 1 for 0 <= k < 2^(n-1).
T(n,k+1) = T(n,k) XOR 2^(n-A001511(n)).
|
|
|
EXAMPLE
|
Triangle 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, 2, 3, 7, 5, 1,
n=4: 0, 8, 12, 4, 6, 14, 10, 2, 3, 11, 15, 7, 5, 13, 9, 1,
n=5: 0, 16, 24, 8, 12, 28, 20, 4, 6, 22, 30, 14, 10, 26, 18, 2, 3, 19, 27, 11, 15, 31, 23, 7, 5, 21, 29, 13, 9, 25, 17, 1,
...
In row n=3, the corresponding binary words of length 3 are 000, 100, 110, 010, 011, 111, 101, and 001 - notice that the most significant bits change the fastest.
|
|
|
MAPLE
|
with(ListTools): with(Bits):
T:= (n, k)-> Join(Reverse(Split(Xor(k, iquo(k, 2)), bits=n))):
|
|
|
PROG
|
(PARI) T(n, k) = fromdigits(Vecrev(binary(bitxor(k, k>>1)), n), 2); \\ Kevin Ryde, Apr 17 2023
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,tabf,base
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
