A360302 T(n,k) is the position of the set encoded in the binary expansion of k within the shortlex order for the powerset of [n]; triangle T(n,k), n>=0, 0<=k<=2^n-1, read by rows.

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

Offset: 0

Author

Alois P. Heinz, Feb 03 2023

Keywords

• nonn
• look
• tabf

Comments

In shortlex order for 2^[n] the subsets are primarily sorted by cardinality and then into lexicographical order.

The set encoded by k consists of the indices of 1-bits (rightmost index is 1).

Row n is a permutation of {0, 1, ..., 2^n-1} whose inverse is in row n of A359941.

Examples

			The subsets of [4] listed in shortlex order (starting at position 0) are: {}, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}.
T(4,0) = T(4,0000_2) = 0: {} is at position 0.
T(4,3) = T(4,0011_2) = 5: {1,2} is at position 5.
T(4,6) = T(4,0110_2) = 8: {2,3} is at position 8.
T(4,7) = T(4,0111_2) = 11: {1,2,3} is at position 11.
T(4,15) = T(4,1111_2) = 15: {1,2,3,4} is at position 15.
Triangle T(n,k) begins:
  0;
  0, 1;
  0, 1, 2, 3;
  0, 1, 2, 4, 3, 5, 6,  7;
  0, 1, 2, 5, 3, 6, 8, 11, 4, 7, 9, 12, 10, 13, 14, 15;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..13, flattened
• Wikipedia, Shortlex order

Crossrefs

Columns k=0-1 give: A000004, A057427.

Row sums give A006516(n) = A000217(A000225(n)).

Row lengths are A000079.

Cf. A082185, A193360, A359941.

Programs

Maple

T:= proc(n) option remember; local h, i, l;
      l:= map(x-> add(2^(i-1), i=x),
         [seq(combinat[choose]([$1..n], i)[], i=0..n)]);
      h(0):=0; for i to nops(l) do h(l[i]):= (i-1) od:
      seq(h(i), i=0..2^n-1)
    end:
seq(T(n), n=0..6);

Formula

T(n,A359941(n,k)) = k = A359941(n,T(n,k)).