A322401 Number of strict integer partitions of n with edge-connectivity 1.

0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 5, 1, 6, 2, 7, 2, 13, 3, 14, 6, 18, 8, 28, 11, 33, 19, 38, 22, 54, 28, 71, 44, 83, 53, 110, 68, 134, 98, 154, 120, 209, 145, 253, 191, 302, 244, 385, 299, 459, 390, 553, 483, 693, 578

Offset: 0

Author

Gus Wiseman, Dec 06 2018

Keywords

• nonn

Comments

The edge-connectivity of an integer partition is the minimum number of parts that must be removed so that the prime factorizations of the remaining parts form a disconnected (or empty) hypergraph.

Examples

			The a(30) = 11 strict integer partitions with edge-connectivity 1:
  (30),
  (10,9,6,5), (12,10,5,3), (14,7,6,3), (15,6,5,4), (15,10,3,2),
  (9,8,6,4,3), (10,9,6,3,2), (12,9,4,3,2), (15,6,4,3,2),
  (10,6,5,4,3,2).
		

Links

• Wikipedia, k-edge-connected graph

Crossrefs

Cf. A095983, A218970, A304714, A304716, A305078, A305079, A322335, A322337, A322387, A322390, A322391, A322393, A322394, A322400.

Programs

Mathematica

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
edgeConn[y_]:=If[Length[csm[primeMS/@y]]!=1,0,Length[y]-Max@@Length/@Select[Union[Subsets[y]],Length[csm[primeMS/@#]]!=1&]];
Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&edgeConn[#]==1&]],{n,30}]