A369605 -id:A369605 - cp's OEIS frontend

A333333 Irregular triangle: T(n,k) gives the number of k-polysticks on edges of the n-cube up to isometries of the n-cube, with 0 <= k <= A001787(n).

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 4, 9, 14, 19, 16, 9, 4, 1, 1, 1, 1, 1, 3, 7, 21, 72, 269, 994, 3615, 12337, 38603, 107720, 259990, 526314, 865217, 1139344, 1225762, 1109138, 857376, 574284, 333484, 169023, 73994, 28222, 9138, 2595, 604, 140, 24, 6, 1, 1

Offset: 1

Peter Kagey, Mar 15 2020

This sequence counts edge-induced connected subgraphs of the n-dimensional hypercube graph, up to automorphisms of the hypercube; A369605 counts vertex-induced such graphs. - Pontus von Brömssen, May 12 2025

Row 3 gives the number of polyforms with n cells on the faces of a rhombic dodecahedron up to rotation and reflection. - Peter Kagey, May 19 2025

			Table begins:
n\k| 0  1  2  3  4   5   6    7    8     9     10     11      12 ...
---+----------------------------------------------------------------
  1| 1, 1;
  2| 1, 1, 1, 1, 1;
  3| 1, 1, 1, 3, 4,  9, 14,  19,  16,    9,     4,     1,      1;
  4| 1, 1, 1, 3, 7, 21, 72, 269, 994, 3615, 12337, 38603, 107720, ...

Code Golf Stack Exchange, Counting polyominoes on (hyper-)cubes
Peter Kagey, Examples of T(3,3) through T(3,8).
Wikipedia, Hypercube
Wikipedia, Polystick

Cf. A001787, A222192, A369605.

T(n,k) = T(n-1,k) for k < n.
T(n,0) = T(n,1) = T(n,2) = T(n,A001787(n)-1) = T(n,A001787(n)) = 1.
A222192(n) = Sum_{k=0..n*2^(n-1)} T(n,k) - Sum_{k=0..(n-1)*2^(n-2)} T(n-1,k) for n >= 2. - Peter Kagey, Jun 19 2023

a(31)-a(40) from Pontus von Brömssen, May 12 2025

a(41)-a(53) from Pontus von Brömssen, May 30 2025

A383973 Irregular triangle: T(n,k) gives the number of connected subsets of k edges of the n-dimensional cross-polytope up to isometries of the polytope, with 0 <= k <= A046092(n-1).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 5, 11, 21, 28, 24, 18, 9, 4, 1, 1, 1, 1, 2, 7, 22, 82, 292, 876, 2023, 3699, 5587, 7099, 7712, 7129, 5668, 3843, 2234, 1099, 475, 169, 57, 16, 5, 1, 1, 1, 1, 2, 7, 25, 114, 584, 3055

Offset: 1

Peter Kagey, May 16 2025

The cross-polytope is also called an orthoplex or a hyperoctahedron.
Connected subsets of edges are also called "polysticks," "polyedges," and "polyforms."
These are "free" polyforms, in that two polyforms are equivalent if one can be mapped to the other using the n!*2^n symmetries of the cross-polytope.

			Triangle begins
 1 | 1;
 2 | 1, 1, 1, 1, 1;
 3 | 1, 1, 2, 5, 11, 21, 28, 24, 18, 9, 4, 1, 1;
 4 | 1, 1, 2, 7, 22, 82, 292, 876, 2023, 3699, 5587, 7099, 7712, 7129, 5668, 3843, 2234, 1099, 475, 169, 57, 16, 5, 1, 1;

Peter Kagey, Illustration of the T(3,3)=5 polysticks on the edges of an octahedron of size 3.
Wikipedia, Cross-polytope
Wikipedia, Polystick

Cf. A046092, A333333 (n-cube), A369605.

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.

Original entry on oeis.org

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

Pontus von Brömssen, Feb 07 2024

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.

			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;
  ...

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

A385385 Irregular triangle read by rows: T(n,k) is the number of polyominoes of size k, i.e., connected subsets of k square cells (or vertices), of the n X n flat torus, up to cyclic shifts and reflections of rows and columns, as well as interchange of rows and columns; 1 <= k <= n^2.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 4, 2, 1, 1, 1, 1, 2, 5, 10, 23, 44, 80, 87, 86, 49, 32, 10, 5, 1, 1, 1, 1, 2, 5, 12, 32, 88, 249, 675, 1699, 3747, 6993, 10538, 12531, 11580, 8458, 4975, 2378, 943, 305, 87, 19, 5, 1, 1

Offset: 1

Pontus von Brömssen, Jun 27 2025

For n = 4, there are 384 automorphisms of the 4 X 4 torus grid graph (it is isomorphic to the 4-dimensional hypercube graph), but here we only consider the subgroup consisting of the 128 symmetries of the 4 X 4 torus. Using the full automorphism group of the torus grid graph would change row 4 to the corresponding row of A369605.

			Triangle begins:
  1;
  1, 1, 1, 1;
  1, 1, 2, 3,  4,  4,  2,  1,  1;
  1, 1, 2, 5, 10, 23, 44, 80, 87, 86, 49, 32, 10, 5, 1, 1;
  ...

Cf. A000105, A369605, A385383 (interchange of rows and columns of the torus not allowed), A385384 (row sums), A385390 (edge subsets).

T(n,k) = A000105(k) if n >= k.

T(n,k) >= A385383(n,k)/2, with equality if and only if k = 2.

A369606 Number of inequivalent connected induced subgraphs of the hypercube graph of dimension n.

Original entry on oeis.org

1, 2, 4, 13, 209, 709191

Offset: 0

Pontus von Brömssen, Jan 27 2024

The null subgraph is not considered to be connected.
See A369605 for details.
In A290758, equivalent subgraphs are counted separately.
A000616 is the corresponding sequence for not necessarily connected subgraphs.

Row sums of A369605.

Cf. A000616, A290758.

a(5) from Pontus von Brömssen, May 14 2025

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).

A384157 Irregular triangle read by rows: T(n,k) is the number of connected induced k-vertex subgraphs of the hyperoctahedral graph of dimension n >= 1 up to automorphisms of the hyperoctahedral graph; 0 <= k <= 2*n.

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 3, 2, 2, 1, 1, 1, 1, 1, 2, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 2, 3, 3, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 2, 3, 3, 4, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 2, 3, 3, 4, 4, 5, 4, 4, 3, 3, 2, 2, 1, 1

Offset: 1

Peter Kagey and Pontus von Brömssen, May 21 2025

In this sequence, the empty graph is considered to be connected.
There are n!*2^n graph automorphisms of the n-hyperoctahedral graph.
The hyperoctahedral graph is also called the "cocktail party graph," and corresponds to the 1-skeleton of the n-dimensional cross-polytope.
Row 3 corresponds to the number of polyominoes on the faces of a cube up to rotation and reflection of the cube.
More generally, this sequence gives the number of k-celled polyforms whose cells are (n-1)-dimensional facets of the n-dimensional hypercube.
An induced subgraph of the hyperoctahedral graph is completely determined (up to automorphisms of the hyperoctahedral graph) by the number i of pairs of antipodal vertices and the number j of vertices whose antipode is not in the subgraph. The subgraph is disconnected if and only if i=1 and j=0. This implies a close relation to A008967 (which also counts disconnected subgraphs); see formula.

			Triangle begins:
  1 | 1, 1, 0;
  2 | 1, 1, 1, 1, 1;
  3 | 1, 1, 1, 2, 2, 1, 1;
  4 | 1, 1, 1, 2, 3, 2, 2, 1, 1;
  5 | 1, 1, 1, 2, 3, 3, 3, 2, 2, 1, 1;
  6 | 1, 1, 1, 2, 3, 3, 4, 3, 3, 2, 2, 1, 1;
  7 | 1, 1, 1, 2, 3, 3, 4, 4, 4, 3, 3, 2, 2, 1, 1;
  8 | 1, 1, 1, 2, 3, 3, 4, 4, 5, 4, 4, 3, 3, 2, 2, 1, 1;
  ...

Eric Weisstein's World of Mathematics, Cocktail Party Graph.
Wikipedia, Cross-polytope

Cf. A008967 (includes disconnected subgraphs), A369605 (hypercube graph), A383973 (edges).

T(n,k) = A008967(n+4,k) if k != 2; T(n,2) = A008967(n+4,2)-1.

G.f.: 1/((1-y)*(1-x*y)*(1-x^2*y)) - x^2*y/(1-y) - 1.

cp's OEIS Frontend

A333333 Irregular triangle: T(n,k) gives the number of k-polysticks on edges of the n-cube up to isometries of the n-cube, with 0 <= k <= A001787(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A383973 Irregular triangle: T(n,k) gives the number of connected subsets of k edges of the n-dimensional cross-polytope up to isometries of the polytope, with 0 <= k <= A046092(n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

A385385 Irregular triangle read by rows: T(n,k) is the number of polyominoes of size k, i.e., connected subsets of k square cells (or vertices), of the n X n flat torus, up to cyclic shifts and reflections of rows and columns, as well as interchange of rows and columns; 1 <= k <= n^2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A369606 Number of inequivalent connected induced subgraphs of the hypercube graph of dimension n.

Views

Author

Keywords

Comments

Crossrefs

Extensions

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

A384157 Irregular triangle read by rows: T(n,k) is the number of connected induced k-vertex subgraphs of the hyperoctahedral graph of dimension n >= 1 up to automorphisms of the hyperoctahedral graph; 0 <= k <= 2*n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula