0,5

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 sequenceA001511(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 (seeA003188) and vice versa.

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.

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

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

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

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.

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

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

T(n,2^n-1) givesA057427.

Cf. alsoA000120,A005811,A363674.

Sequence in context:A115352A275808A038554*A356120A100329A193535

Adjacent sequences:A362157A362158A362159*A362161A362162A362163

nonn,easy,tabf,base

Valentin Bakoev,Apr 10 2023

approved