A322389 Vertex-connectivity of the integer partition with Heinz number n.

0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 0, 0, 0, 0, 2, 0, 2, 0, 1, 0, 2, 0, 0, 0, 2, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 2, 0, 1, 0, 2, 0, 1, 0, 0, 0, 2, 0, 2, 0, 0, 0, 0, 0, 2, 0, 1, 0, 1, 0, 0, 0, 2

Offset: 1

Author

Gus Wiseman, Dec 05 2018

Keywords

• nonn

Comments

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).

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 integer partition (6,4,3) with Heinz number 455 does not become disconnected or empty if 2 is divided out giving (3,3), or if 3 is divided out giving (4,2), but it does become disconnected or empty if both 2 and 3 are divided out giving (); so a(455) = 2.
195 is the Heinz number of (6,3,2), corresponding to the multiset partition {{1},{2},{1,2}}. Removing the vertex 1 gives {{2},{2}}, while removing 2 gives {{1},{1}}. These are both connected, so both vertices must be removed to obtain a disconnected or empty multiset partition; hence a(195) = 2.
		

Links

• Wikipedia, k-vertex-connected graph

Crossrefs

Cf. A003963, A013922, A056239, A095983, A112798, A302242, A304716, A305078, A305079, A322335, A322336, A322338, A322387, A322388, A322390.

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]]];
Array[vertConn@*primeMS,100]