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.

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

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 Russian), p. 31, Algorithm 1.13.

F. Ruskey, Combinatorial Generation. Working Version (1j-CSC 425/520), 2003, pp. 120-121.

Links

Valentin Bakoev, Rows n = 0..15, flattened

Valentin Bakoev, Mirror (left-recursive) Gray Code, Mathematics and Informatics, Vol. 66, Number 6, pp. 559-578, (2023).

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(k)).

A000120(T(n,n)) = A005811(n). - Alois P. Heinz, Jun 27 2023

T(n, k) = A088208(n, k) - 1. - Andrey Zabolotskiy, Dec 06 2024

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))):
seq(seq(T(n, k), k=0..2^n-1), n=0..6);  # Alois P. Heinz, Jun 05 2023

Prog

(PARI) T(n, k) = fromdigits(Vecrev(binary(bitxor(k, k>>1)), n), 2); \\ Kevin Ryde, Apr 17 2023

Crossrefs

Cf. A003188 (Gray code), A006516 (row sums), A000004 (column k=0), A000079 (column k=1), A088208.

T(n,2^n-1) gives A057427.

Cf. also A000120, A005811, A363674.

Sequence in context: A115352 A275808 A038554 * A356120 A100329 A193535

Adjacent sequences: A362157 A362158 A362159 * A362161 A362162 A362163

Keyword

nonn,easy,tabf,base

Author

Valentin Bakoev, Apr 10 2023

Status

approved