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.
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 \ | |
--------------------------+-----------------+----------------
(The N/A entry corresponds to rows 2^n of Pascal's triangle; A345135 comes close.)
KEYWORD
nonn,tabf,more
AUTHOR
Pontus von Brömssen, Jan 27 2024
STATUS
approved