OFFSET
1,2
COMMENTS
For a given graph G, the set of partitions satisfying the above condition ordered by refinement form a lattice known variously as the lattice of flats, the lattice of contractions, the bond lattice, the connectivity lattice, and the lattice of connected set partitions.
LINKS
Frank Simon, Peter Tittmann, and Martin Trinks, Counting Connected Set Partitions, Electronic Journal of Combinatorics, Vol 18, (2011).
Andrew Vince, Counting connected sets and connected partitions of a graph, Australasian Journal of Combinatorics, 67(2) (2017), 281-293.
FORMULA
a(n) = Sum_{r_1^m_1+r_2^m_2+...+r_k^m_k = n} n!/(Product_{i=1..k} r_i! * Product_{i=1..k} m_i!) * Product_{i=1..k} A001187(r_i) * 2^(binomial(n,2) - Sum_{i=1..k} binomial(r_i,2)) where the sum is over all integer partitions of n and r_i^m_i denotes m_i copies of the summand r_i.
MATHEMATICA
nn = 15; setpartitionsoftype[type_] := Total[type]!/(Apply[Times, Table[type[[i]]!, {i, 1, Length[type]}]]* Apply[Times, Tally[type][[All, 2]]!]); a[x_] := Sum[2^Binomial[n, 2] x^n/n!, {n, 0, nn}]; connected =Drop[Range[0, nn]! CoefficientList[Series[Log[a[x]], {x, 0, nn}], x], 1]; connectedoftype[type_] := Apply[Times, connected[[type]]]; numberofedgesoftype[type_] := Binomial[Total[type], 2] - Sum[Binomial[type[[i]], 2], i, 1, Length[type]}]; Table[Map[setpartitionsoftype[#]*connectedoftype[#]*2^numberofedgesoftype[#] &, Partitions[n]] // Total, {n, 1, nn}]
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, May 07 2024
STATUS
approved