A320430 Number of set partitions of [n] where the elements of each non-singleton block are pairwise coprime.

1, 1, 2, 5, 10, 37, 60, 295, 658, 2621, 5368, 38535, 66506, 551529, 1234264, 5004697, 13721836, 143935131, 256835337, 2971237021, 6485081140, 35162930303, 95872321543, 1315397878401, 2399236456202, 25866803180347, 72374386475590, 563368417647305, 1479943119911866

Offset

0,3

Comments

Two or more numbers are pairwise coprime if no pair of them has a common divisor > 1.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..38

Example

The a(4) = 10 set partitions: 1|2|3|4, 14|2|3, 13|2|4, 12|3|4, 1|23|4, 1|2|34, 134|2, 123|4, 14|23, 12|34.

Mathematica

spsu[_, {}]:={{}}; spsu[foo_, set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@spsu[Select[foo, Complement[#, Complement[set, s]]=={}&], Complement[set, s]]]/@Cases[foo, {i, ___}];
Table[Length[spsu[Select[Subsets[Range[n]], Length[#]==1||CoprimeQ@@#&], Range[n]]], {n, 10}]

Crossrefs

Cf. A000110, A000258, A008277, A051424, A085945, A186974, A187106, A302569, A303139, A320424, A320426, A320423, A333517.

Sequence in context: A056300 A326006 A144636 * A018418 A363429 A290032

Adjacent sequences: A320427 A320428 A320429 * A320431 A320432 A320433

Keyword

nonn

Author

Gus Wiseman, Jan 08 2019

Extensions

a(14)-a(15) from Alois P. Heinz, Jan 08 2019

a(16) from Alois P. Heinz, Mar 26 2020

a(17)-a(24) from Giovanni Resta, Mar 27 2020

a(25)-a(28) from Alois P. Heinz, Aug 03 2023

Status

approved