login
A322401
Number of strict integer partitions of n with edge-connectivity 1.
0
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,12
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.
EXAMPLE
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).
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}]
KEYWORD
nonn
AUTHOR
Gus Wiseman, Dec 06 2018
STATUS
approved