A191249 Triangular array T(n,k) read by rows: number of labeled relations of the n-set with exactly k connected components.

2, 12, 4, 432, 72, 8, 61344, 3888, 288, 16, 32866560, 665280, 21600, 960, 32, 68307743232, 407306880, 4328640, 95040, 2880, 64, 561981464819712, 965518299648, 2948037120, 21893760, 362880, 8064, 128

Offset: 1

Author

Geoffrey Critzer, May 28 2011

Keywords

• nonn
• tabl

Comments

T(n,k) is the number of binary relations R on {1,2,...,n} such that the reflexive, symmetric and transitive closure of R is an equivalence relation with exactly k classes.

Row sums are A002416 = 2^(n^2).

Column 1 is A062738.

T(n,n) = 2^n is the number of binary relations that are a subset of the diagonal relation.

Examples

			2
12       4
432      72     8
61344    3888   288   16
32866560 665280 21600 960 32
		

Programs

Mathematica

a=Sum[2^(n^2) x^n/n!,{n,0,10}];
Transpose[Table[Drop[Range[0, 10]! CoefficientList[Series[Log[a]^n/n!, {x, 0, 10}],x],1], {n, 1, 10}]] // Grid

Formula

E.g.f. for column k: log(A(x))^k/k! where A(x) is the E.g.f. for A002416