login
A371126
Let G be a simple labeled graph with vertex set [n] and let P be a set partition of [n]. Then a(n) is the number of ordered pairs (G,P) such that for all x,y in [n], if x and y are in the same block of P then there is a path in G from x to y.
0
1, 3, 24, 470, 21432, 2213968, 509257232, 257475122096, 283161056661248, 671705854972452224, 3413655802591871457024, 36958970631216278283126272, 848441332034601400642087930880, 41129897405317524733456924395326464, 4195586359269235721058830388934374641664
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}]
CROSSREFS
Sequence in context: A002832 A233151 A236466 * A185970 A279165 A336577
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, May 07 2024
STATUS
approved