A322390 Number of integer partitions of n with vertex-connectivity 1.

0, 1, 1, 2, 1, 3, 1, 4, 2, 5, 1, 8, 1, 7, 3, 11, 1, 14, 2, 18, 7, 21, 6, 35, 14, 43, 28, 65, 42, 96, 70, 141, 120, 205, 187, 315, 286, 445, 445, 657

Offset: 1

Author

Gus Wiseman, Dec 05 2018

Keywords

• nonn
• more

Comments

The vertex-connectivity of an integer partition is the minimum number of primes that must be divided out (and any parts then equal to 1 removed) so that the prime factorizations of the remaining parts form a disconnected (or empty) hypergraph.

Examples

			The a(14) = 7 integer partitions are (842), (8222), (77), (4442), (44222), (422222), (2222222).
The a(18) = 14 integer partitions:
  (9,9), (16,2),
  (8,8,2), (10,6,2),
  (8,4,4,2), (9,3,3,3),
  (4,4,4,4,2), (8,4,2,2,2),
  (3,3,3,3,3,3), (4,4,4,2,2,2), (8,2,2,2,2,2),
  (4,4,2,2,2,2,2),
  (4,2,2,2,2,2,2,2),
  (2,2,2,2,2,2,2,2,2).
		

Links

• Wikipedia, k-vertex-connected graph

Crossrefs

Cf. A013922, A054921, A095983, A304714, A304716, A305078, A305079, A322335, A322338, A322387, A322389, A322391.

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]]]]]]]]];
vertConn[y_]:=If[Length[csm[primeMS/@y]]!=1,0,Min@@Length/@Select[Subsets[Union@@primeMS/@y],Function[del,Length[csm[DeleteCases[DeleteCases[primeMS/@y,Alternatives@@del,{2}],{}]]]!=1]]];
Table[Length[Select[IntegerPartitions[n],vertConn[#]==1&]],{n,20}]