A106240 Triangle read by rows: T(n,m) = number of unlabeled cographs on n nodes with m connected components.

1, 1, 1, 2, 1, 1, 5, 3, 1, 1, 12, 7, 3, 1, 1, 33, 20, 8, 3, 1, 1, 90, 55, 22, 8, 3, 1, 1, 261, 162, 63, 23, 8, 3, 1, 1, 766, 477, 188, 65, 23, 8, 3, 1, 1, 2312, 1450, 564, 196, 66, 23, 8, 3, 1, 1, 7068, 4446, 1732, 590, 198, 66, 23, 8, 3, 1, 1, 21965, 13858, 5384, 1824, 598, 199, 66, 23, 8, 3, 1, 1

Offset

1,4

Links

Alois P. Heinz, Rows n = 1..141, flattened

Washington Bomfim, Illustration of this sequence

Formula

T(n, m) = sum over the partitions of n with m parts: 1K1 + 2K2 + ... + nKn = n, K1 + K2 + ... + Kn = m, of Product_{i=1..n} binomial(A000669(i)+Ki-1, Ki).

Example

T(10,8) = 3 because the partitions of 10 with 8 parts are 31111111 and 22111111. The partition 31111111 corresponds to 2 graphs and the partition 22111111 corresponds to only one.
T(n,m) = 1, if and only if m>=n-1. Because A000669(1)=A000669(2)=1, the partitions of n with all parts <=2 correspond to summands = 1. If there is only a summand (or partition), the total is equal to 1. It is clear that for m>=n-1 there is only one partition of n with exactly m parts.
Triangle begins:
   1,
   1,  1,
   2,  1,  1,
   5,  3,  1, 1,
  12,  7,  3, 1, 1,
  33, 20,  8, 3, 1, 1,
  90, 55, 22, 8, 3, 1, 1,

Crossrefs

Cf. A000669 (first column), A000084 (row sums), A201922.

Sequence in context: A124328 A368487 A055818 * A340561 A097615 A288386

Adjacent sequences: A106237 A106238 A106239 * A106241 A106242 A106243

Keyword

nonn,tabl

Author

Washington Bomfim, May 06 2005

Status

approved