A370609 Triangle read by rows: T(n,k) is the number of labeled graphs with vertex set [n] that are reachable in k (but no fewer) steps from a given graph on [n], where a step consists of choosing a subset S of [n] and replacing the subgraph induced by S with its complement, 0 <= k <= n-1.

1, 1, 1, 1, 4, 3, 1, 11, 40, 12, 1, 26, 280, 657, 60, 1, 57, 1491, 13447, 17412, 360, 1, 120, 6930, 178297, 1127388, 781896, 2520

Offset

1,5

Comments

This is the labeled version of A370072. Here, in contrast to A370072, it does not matter which graph we start with.

Define a graph on 2^(n*(n-1)/2) nodes, where each node corresponds to a labeled graph on [n] and two nodes are adjacent if the symmetric difference of the edge sets of the corresponding graphs equals the set of edges of a complete graph on a subset of [n]. This graph is vertex transitive, and T(n,k) is the number of nodes at distance k from a given node. The independence number of this graph is studied in Alon (2024).

Links

Table of n, a(n) for n=1..28.

Noga Alon, Graph-codes, European Journal of Combinatorics 116 (2024), Article ID 103880; arXiv version.

Example

Triangle begins:
  1;
  1, 1;
  1, 4, 3;
  1, 11, 40, 12;
  1, 26, 280, 657, 60;
  1, 57, 1491, 13447, 17412, 360;
  1, 120, 6930, 178297, 1127388, 781896, 2520;
  ...

Crossrefs

Cf. A000295 (column k=1), A006125 (row sums), A370072.

Sequence in context: A128813 A109062 A112493 * A010305 A308326 A098234

Adjacent sequences: A370606 A370607 A370608 * A370610 A370611 A370612

Keyword

nonn,tabl,more

Author

Pontus von Brömssen, Feb 23 2024

Status

approved