A369605 Irregular triangle read by rows: T(n,k) is the number of inequivalent connected induced k-vertex subgraphs 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, 5, 11, 19, 36, 37, 41, 24, 18, 6, 4, 1, 1

Offset

0,11

Comments

Two subgraphs are equivalent if there is an automorphism of the hypercube graph that takes one to the other.

Two isomorphic subgraphs may both be counted. For example, 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. This implies that T(4,5) > A369997(4,5). (In A369997, the subgraphs are counted up to isomorphism.)

Also, number of free k-celled polycubes in n dimensions, whose width in any coordinate direction is at most 2.

Also, number of k-celled polyominoes whose cells are subsets of the (n-1)-dimensional facets of the n-dimensional cross-polytope (or orthoplex). (See A049540.)

A039754 is the corresponding sequence for not necessarily connected subgraphs.

Links

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

Formula

T(n,k) = A049540(k) for k <= n+1.

T(n,k) = A039754(n,k) for k > 2^n-n.

Example

Triangle begins:
  1;
  1, 1;
  1, 1, 1, 1;
  1, 1, 1, 3, 2,  3,  1,  1;
  1, 1, 1, 3, 5, 11, 19, 36, 37, 41, 24, 18, 6, 4, 1, 1;
  ...
There are T(3,4) = 3 inequivalent connected induced 4-vertex subgraphs of the 3-cube: four vertices of a 2-dimensional face or three vertices of a face together with a vertex from the opposite face, adjacent to either of two inequivalent vertices from the first face.

Crossrefs

Cf. A049540 (main diagonal).

Different ways of counting induced subgraphs in the hypercube graph (totals or by number of vertices):

\ Subgraphs | All | Connected

Symmetries \ | |

--------------------------+-----------------+----------------

None | A001146/ N/A | A290758/A369999

Automorphisms of the cube | A000616/A039754 | A369606/A369605

Isomorphism | A369996/A369995 | A369998/A369997

(The N/A entry corresponds to rows 2^n of Pascal's triangle; A345135 comes close.)

Sequence in context: A191390 A309698 A369997 * A085747 A106693 A107335

Adjacent sequences: A369602 A369603 A369604 * A369606 A369607 A369608

Keyword

nonn,tabf,more

Author

Pontus von Brömssen, Jan 27 2024

Status

approved