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

Author

Valentin Bakoev, Apr 10 2023

Keywords

• nonn
• easy
• tabf
• base

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.

Examples

			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.
		

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

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.

Programs

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

PARI

T(n,k) = fromdigits(Vecrev(binary(bitxor(k,k>>1)), n), 2); \\ Kevin Ryde, Apr 17 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