A371126 - OEIS

%I #43 May 11 2024 09:41:52

%S 1,3,24,470,21432,2213968,509257232,257475122096,283161056661248,

%T 671705854972452224,3413655802591871457024,36958970631216278283126272,

%U 848441332034601400642087930880,41129897405317524733456924395326464,4195586359269235721058830388934374641664

%N 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.

%C 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.

%H Frank Simon, Peter Tittmann, and Martin Trinks, <a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p14">Counting Connected Set Partitions</a>, Electronic Journal of Combinatorics, Vol 18, (2011).

%H Andrew Vince, <a href="https://ajc.maths.uq.edu.au/pdf/67/ajc_v67_p281.pdf">Counting connected sets and connected partitions of a graph</a>, Australasian Journal of Combinatorics, 67(2) (2017), 281-293.

%F 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.

%t 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}]

%Y Cf. A001187, A281263.

%K nonn

%O 1,2

%A _Geoffrey Critzer_, May 07 2024