A382755 Irregular triangle read by rows: Let k encode the edges of an n-vertex graph by taking edges (u,v), with u < v, in lexicographic order ((0,1), ..., (0,n-1), (1,2), ..., (1,n-1), ..., (n-1,n)) and adding each edge to the graph if the corresponding binary digit of k (starting with the least significant digit) is 1. T(n,k) is the smallest nonnegative integer that encodes the same unlabeled n-vertex graph as k, 0 <= k < n*(n-1)/2.

0, 0, 0, 1, 0, 1, 1, 3, 1, 3, 3, 7, 0, 1, 1, 3, 1, 3, 3, 7, 1, 3, 3, 11, 12, 13, 13, 15, 1, 3, 12, 13, 3, 11, 13, 15, 3, 7, 13, 15, 13, 15, 30, 31, 1, 12, 3, 13, 3, 13, 11, 15, 3, 13, 7, 15, 13, 30, 15, 31, 3, 13, 13, 30, 7, 15, 15, 31, 11, 15, 15, 31, 15, 31, 31, 63

Offset: 0

Author

Pontus von Brömssen, Apr 04 2025

Keywords

• nonn
• tabf

Comments

In the encoding given by A382754, the code of the graph corresponding to T(n,k) is 2^(n*(n-1)/2) + T(n,k) if n > 0.

The first case where a row is not an initial segment of the next row is T(4,11) = 11 != 7 = T(5,11).

Examples

			Triangle begins:
  0;
  0;
  0, 1;
  0, 1, 1, 3, 1, 3, 3, 7;
  ...
For n = 5, k = 11, 11 is 1011 in binary, which encodes the 5-vertex graph with edges (0,1), (0,2), and (0,4) (3 being an isolated vertex). The smallest code for an isomorphic graph is obtained by substituting the edge (0,3) for (0,4), resulting in the code 111 in binary, i.e., T(5,11) = 7.
		

Crossrefs

Cf. A382281, A382754.

Formula

T(n,k) <= k with equality if and only if 2^(n*(n-1)/2) + k is in A382754.