login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A304716
Number of integer partitions of n whose distinct parts are connected.
69
1, 2, 2, 3, 2, 5, 2, 6, 4, 9, 3, 15, 4, 18, 12, 25, 11, 41, 17, 54, 36, 72, 44, 113, 69, 145, 113, 204, 153, 302, 220, 394, 343, 541, 475, 771, 662, 1023, 968, 1398, 1314, 1929, 1822, 2566, 2565, 3440, 3446, 4677, 4688, 6187, 6407, 8216, 8544, 10975, 11436
OFFSET
1,2
COMMENTS
Given a finite set S of positive integers greater than one, let G(S) be the simple labeled graph with vertex set S and edges between any two vertices with a common divisor. For example, G({6,14,15,35}) is a 4-cycle. A multiset S is said to be connected if G(S) is a connected graph.
FORMULA
For n > 1, a(n) = A218970(n) + 1. - Gus Wiseman, Dec 04 2018
EXAMPLE
The a(12) = 15 connected integer partitions and their corresponding connected multiset multisystems (see A112798, A302242) are the following.
(12): {{1,1,2}}
(6 6): {{1,2},{1,2}}
(8 4): {{1,1,1},{1,1}}
(9 3): {{2,2},{2}}
(10 2): {{1,3},{1}}
(4 4 4): {{1,1},{1,1},{1,1}}
(6 3 3): {{1,2},{2},{2}}
(6 4 2): {{1,2},{1,1},{1}}
(8 2 2): {{1,1,1},{1},{1}}
(3 3 3 3): {{2},{2},{2},{2}}
(4 4 2 2): {{1,1},{1,1},{1},{1}}
(6 2 2 2): {{1,2},{1},{1},{1}}
(4 2 2 2 2): {{1,1},{1},{1},{1},{1}}
(2 2 2 2 2 2): {{1},{1},{1},{1},{1},{1}}
(1 1 1 1 1 1 1 1 1 1 1 1): {{},{},{},{},{},{},{},{},{},{},{},{}}
MATHEMATICA
zsm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[Less@@#, GCD@@s[[#]]]>1&]}, If[c==={}, s, zsm[Union[Append[Delete[s, List/@c[[1]]], LCM@@s[[c[[1]]]]]]]]];
Table[Length[Select[IntegerPartitions[n], Length[zsm[Union[#]]]===1&]], {n, 30}]
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 17 2018
EXTENSIONS
Name changed to distinguish from A218970 by Gus Wiseman, Dec 04 2018
STATUS
approved