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.

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

Author

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

Keywords

• nonn
• tabf

Comments

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.

Examples

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

Links

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

Crossrefs

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

Formula

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.