A389985 Irregular triangle read by rows: T(n,k) is the number of partitions of the vertex set of the n-cocktailparty graph into k connected subsets, 1 <= k <= 2*n.

0, 1, 1, 6, 4, 1, 1, 28, 71, 50, 12, 1, 1, 123, 848, 1380, 822, 212, 24, 1, 1, 506, 8705, 29575, 34854, 18172, 4690, 620, 40, 1, 1, 2041, 83475, 557406, 1188655, 1092317, 504968, 127452, 18175, 1450, 60, 1

Offset

1,4

Comments

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

Links

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

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

Formula

T(n,k) = Sum_{j=0..min(k,2*n-k)} (-1)^j*binomial(n,j)*A008277(2*(n-j),k-j).

Example

Triangle begins:
  n\k| 1    2     3      4       5       6      7      8     9   10 11 12
  ---+-------------------------------------------------------------------
  1  | 0    1
  2  | 1    6     4      1
  3  | 1   28    71     50      12       1
  4  | 1  123   848   1380     822     212     24      1
  5  | 1  506  8705  29575   34854   18172   4690    620    40    1
  6  | 1 2041 83475 557406 1188655 1092317 504968 127452 18175 1450 60  1

Crossrefs

Cf. A008277, A124133 (column k=2 for n>=3), A282010 (row sums), A389983.

Sequence in context: A106333 A104748 A117335 * A389983 A319555 A244980

Adjacent sequences: A389982 A389983 A389984 * A389986 A389987 A389988

Keyword

nonn,tabf

Author

Pontus von Brömssen, Oct 22 2025

Status

approved