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

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

Links

Table of n, a(n) for n=0..75.

Formula

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

Example

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.

Sequence in context: A333334 A205145 A061892 * A038573 A246591 A173465

Adjacent sequences: A382752 A382753 A382754 * A382756 A382757 A382758

Keyword

nonn,tabf

Author

Pontus von Brömssen, Apr 04 2025

Status

approved