A359941 Irregular triangle read row by row. The k-th row are integers from 0 to 2^k-1 in base 2 ordered in graded reverse lexicographical order.

0, 0, 1, 0, 1, 2, 3, 0, 1, 2, 4, 3, 5, 6, 7, 0, 1, 2, 4, 8, 3, 5, 9, 6, 10, 12, 7, 11, 13, 14, 15, 0, 1, 2, 4, 8, 16, 3, 5, 9, 17, 6, 10, 18, 12, 20, 24, 7, 11, 19, 13, 21, 25, 14, 22, 26, 28, 15, 23, 27, 29, 30, 31, 0, 1, 2, 4, 8, 16, 32, 3, 5, 9, 17, 33, 6

Offset: 0

Author

Jean Liénardy, Jan 19 2023

Keywords

• nonn
• base
• look
• tabf
• easy

Comments

The integers in the k-th row are first ordered by the number of 1 in their binary representation (Hamming weight). Elements of the same Hamming weight are ordered by reverse colexicographical order.

The k-th row corresponds to the graded lexicographical order of monomials. For example, with k=3, the monomial are ordered as {1, x0, x1, x2, x1*x0, x2*x0, x2*x1, x2*x1*x0}. This ordering of monomial leads to efficient implementation of polynomial long division (see Links section).

Examples

			As an irregular triangle:
  0;
  0, 1;
  0, 1, 2, 3;
  0, 1, 2, 4, 3, 5, 6, 7;
  0, 1, 2, 4, 8, 3, 5, 9, 6, 10, 12, 7, 11, 13, 14, 15;
  ...
For k = 4, the graded lexicographical order of integers 0..15 written in base 2 is
  0000
  0001, 0010, 0100, 1000,
  0011, 0101, 1001, 0110, 1010, 1100,
  0111, 1011, 1101, 1110,
  1111
Note that 1001 < 0110 as the least significant digit on which they differ is the last one, and 1 < 0 due to the reverse colexicographical ordering.
		

Links

• Alois P. Heinz, Rows n = 0..13, flattened
• Jean Liénardy, C++ program
• Wikipedia, Monomial order

Crossrefs

Cf. A023443, A082185, A360302.

Programs

Maple

T:= n-> map(x-> add(2^(i-1), i=x), [seq(
    combinat[choose]([$1..n], i)[], i=0..n)])[]:
seq(T(n), n=0..6);  # Alois P. Heinz, Feb 03 2023

Formula

T(n,A360302(n,k)) = k = A360302(n,T(n,k)). - Alois P. Heinz, Feb 06 2023