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,6

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

Links

Alois P. Heinz, Rows n = 0..13, flattened

Jean Liénardy, C++ program

Wikipedia, Monomial order

Formula

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

Example

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.

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

Prog

(C++) See Links section.

Crossrefs

Cf. A023443, A082185, A360302.

Sequence in context: A274650 A294648 A356784 * A360302 A351939 A170899

Adjacent sequences: A359938 A359939 A359940 * A359942 A359943 A359944

Keyword

nonn,base,look,tabf,easy

Author

Jean Liénardy, Jan 19 2023

Status

approved