A369997 -id:A369997 - cp's OEIS frontend

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, 1, 1, 1, 3, 5, 17, 44, 158, 493, 1628, 4670, 12266, 27043, 51018, 79042, 103179, 112219, 105232, 84045, 59021, 35533, 19114, 8769, 3716, 1311, 468, 130, 47, 10, 5, 1, 1

Offset: 0

Pontus von Brömssen, Jan 27 2024

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.

			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.

Cf. A049540 (main diagonal), A333333 (edge-induced subgraphs).
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.)

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

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

Row 5 from Pontus von Brömssen, May 14 2025

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

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 3, 6, 3, 3, 1, 1, 1, 1, 2, 3, 7, 12, 26, 42, 63, 54, 49, 27, 19, 6, 4, 1, 1

Offset: 0

Pontus von Brömssen, Feb 07 2024

			Triangle begins:
  1, 1;
  1, 1, 1;
  1, 1, 2, 1, 1;
  1, 1, 2, 3, 6,  3,  3,  1,  1;
  1, 1, 2, 3, 7, 12, 26, 42, 63, 54, 49, 27, 19, 6, 4, 1, 1;
  ...

Cf. A039754 (up to automorphisms of the hypercube), A369996 (row sums), A369997 (connected subgraphs).

A369998 Number of connected induced subgraphs, up to isomorphism, of the hypercube graph of dimension n.

Original entry on oeis.org

1, 2, 4, 13, 194

Offset: 0

Pontus von Brömssen, Feb 07 2024

The null subgraph is not considered to be connected.

In A369606, 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 a(4) = 194 < A369606(4) = 209. 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.

Row sums of A369997.

Cf. A290758, A369606 (up to automorphisms of the hypercube), A369996 (not necessarily connected subgraphs).

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

Original entry on oeis.org

1, 2, 1, 4, 4, 4, 1, 8, 12, 24, 38, 48, 28, 8, 1, 16, 32, 96, 280, 784, 1952, 4304, 7280, 8720, 7136, 4192, 1804, 560, 120, 16, 1

Offset: 0

Pontus von Brömssen, Feb 07 2024

			Triangle begins:
   1;
   2,  1;
   4,  4,  4,   1;
   8, 12, 24,  38,  48,   28,    8,    1;
  16, 32, 96, 280, 784, 1952, 4304, 7280, 8720, 7136, 4192, 1804, 560, 120, 16, 1;
  ...

Cf. A290758 (row sums), A369605 (up to automorphisms of the hypercube), A369997 (up to isomorphism).

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Examples

Crossrefs

A369998 Number of connected induced subgraphs, up to isomorphism, of the hypercube graph of dimension n.

Views

Author

Keywords

Comments

Crossrefs

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

Views

Author

Keywords

Examples

Crossrefs