A369997 Irregular triangle read by rows: T(n,k) is the number of connected induced k-vertex subgraphs, up to isomorphism, of the hypercube graph of dimension n >= 0, 1 <= k <= 2^n.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 3, 1, 1, 1, 1, 1, 3, 4, 9, 15, 31, 35, 40, 24, 18, 6, 4, 1, 1

Offset

0,11

Comments

In A369605, two isomorphic subgraphs may both be counted, namely if there is no automorphism of the hypercube graph that takes one to the other. The first difference is T(4,5) = 4 < A369605(4,5) = 5. The path with 5 vertices is an induced subgraph of the 4-dimensional hypercube in two inequivalent ways: one that is contained in a 3-dimensional subcube and one that is not.

Links

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

Example

Triangle begins:
  1;
  1, 1;
  1, 1, 1, 1;
  1, 1, 1, 3, 2, 3,  1,  1;
  1, 1, 1, 3, 4, 9, 15, 31, 35, 40, 24, 18, 6, 4, 1, 1;
  ...

Crossrefs

Cf. A369605 (up to automorphisms of the hypercube), A369995 (not necessarily connected subgraphs), A369998 (row sums), A369999.

Sequence in context: A103497 A191390 A309698 * A369605 A085747 A106693

Adjacent sequences: A369994 A369995 A369996 * A369998 A369999 A370000

Keyword

nonn,tabf,more

Author

Pontus von Brömssen, Feb 07 2024

Status

approved