cp's OEIS Frontend

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

%I A322389 #5 Dec 06 2018 06:52:10
%S A322389 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,
%T A322389 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,
%U A322389 0,0,2,0,2,0,0,0,0,0,2,0,1,0,1,0,0,0,2
%N A322389 Vertex-connectivity of the integer partition with Heinz number n.
%C A322389 The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).
%C A322389 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.
%H A322389 Wikipedia, <a href="https://en.wikipedia.org/wiki/K-vertex-connected_graph">k-vertex-connected graph</a>
%e A322389 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.
%e A322389 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.
%t A322389 primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
%t A322389 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]]]]]]]]];
%t A322389 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]]];
%t A322389 Array[vertConn@*primeMS,100]
%Y A322389 Cf. A003963, A013922, A056239, A095983, A112798, A302242, A304716, A305078, A305079, A322335, A322336, A322338, A322387, A322388, A322390.
%K A322389 nonn
%O A322389 1,13
%A A322389 _Gus Wiseman_, Dec 05 2018