A322391 Number of integer partitions of n with edge-connectivity 1.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 3, 2, 3, 3, 9, 3, 14, 8, 17, 13, 35, 17, 49, 35, 67, 53, 114, 69

Offset

1,11

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.

Links

Table of n, a(n) for n=1..30.

Wikipedia, k-edge-connected graph

Example

The a(20) = 8 integer partitions:
  (20),
  (12,3,3,2), (9,6,3,2), (8,6,3,3),
  (6,4,4,3,3),
  (6,4,3,3,2,2), (6,3,3,3,3,2),
  (6,3,3,2,2,2,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], edgeConn[#]==1&]], {n, 20}]

Crossrefs

Cf. A007718, A013922, A054921, A095983, A218970, A275307, A304716, A305078, A305079, A322335, A322336, A322387, A322390.

Sequence in context: A158206 A364062 A164988 * A201592 A363757 A354606

Adjacent sequences: A322388 A322389 A322390 * A322392 A322393 A322394

Keyword

nonn,more

Author

Gus Wiseman, Dec 05 2018

Status

approved