A384157 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,12

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.

LINKS

Table of n, a(n) for n=1..80.

Eric Weisstein's World of Mathematics, Cocktail Party Graph.

Wikipedia, Cross-polytope

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.

EXAMPLE

Triangle begins:

1 | 1, 1, 0;

2 | 1, 1, 1, 1, 1;

3 | 1, 1, 1, 2, 2, 1, 1;