1,4

The formula T(n,m) = sum over the partitions of n with m parts: 1K1+2K2+ ... +nKn, of product_{1=<i<=n}C(f(i)+Ki-1, Ki), can be used to count any unlabeled graph of order n, with m components, if f(i) is the number of non-isomorphic connected components of order i. (In general f denotes a sequence that counts unlabeled connected combinatorial objects.)

Washington Bomfim, Illustration of this sequence

Washington Bomfim, Illustration of A106238

Washington Bomfim, Illustration of A106239

Triangle read by rows: T(n, m) = sum over the partitions of n with m parts: 1K1+2K2+ ... +nKn, of product_{1=<i<=n}C(A000669(i)+Ki-1, Ki).

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,

Cf. A000669.

Sequence in context: A047884 A124328 A055818 this_sequence A097615 A062993 A105556

Adjacent sequences: A106237 A106238 A106239 this_sequence A106241 A106242 A106243

nonn,tabl

Washington Bomfim (webonfim(AT)bol.com.br), May 06 2005