A389983 Irregular triangle read by rows: T(n,k) is the number of partitions of the vertex set of the labeled n-dimensional hypercube graph into k connected subsets, 1 <= k <= 2^n.

1, 1, 1, 1, 6, 4, 1, 1, 63, 268, 345, 202, 66, 12, 1, 1, 10056, 280736, 1741230, 4667148, 6945848, 6531432, 4201440, 1946016, 669652, 173712, 33920, 4888, 496, 32, 1

Offset

0,5

Comments

Such partitions of a graph are called graph compositions by Knopfmacher and Mays.

Links

Table of n, a(n) for n=0..30.

A. Knopfmacher and M. E. Mays, Graph Compositions I: Basic Enumeration, Integers 1 (2001), A4.

Formula

T(n,1) = T(n,2^n) = 1.

T(n,2^n-1) = n*2^(n-1) for n >= 1.

Example

Triangle begins:
  n\k| 1  2   3   4   5  6  7  8
  ---+--------------------------
  0  | 1
  1  | 1  1
  2  | 1  6   4   1
  3  | 1 63 268 345 202 66 12  1

Crossrefs

Cf. A058975 (row sums), A389984 (column k=2), A389985.

Sequence in context: A104748 A117335 A389985 * A319555 A244980 A394104

Adjacent sequences: A389980 A389981 A389982 * A389984 A389985 A389986

Keyword

nonn,tabf,more

Author

Pontus von Brömssen, Oct 22 2025

Status

approved