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,4

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.

Links

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

Wikipedia, k-vertex-connected graph

Example

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).

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}]

Crossrefs

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

Sequence in context: A101279 A361735 A064576 * A113308 A325332 A358195

Adjacent sequences: A322387 A322388 A322389 * A322391 A322392 A322393

Keyword

nonn,more

Author

Gus Wiseman, Dec 05 2018

Status

approved