A320424 Number of set partitions of {1,...,n} where each block's elements are relatively prime.

1, 1, 1, 2, 4, 13, 31, 140, 480, 2306, 9179, 58209, 249205, 1802970, 9463155, 63813439, 389176317, 3415876088, 20506436732, 195865505549, 1353967583125, 12006363947433, 93067012435816, 1019489483393439, 7779097711766093, 86684751695545733, 766357409555622203

Offset: 0

Author

Gus Wiseman, Jan 08 2019

Keywords

• nonn

Comments

Two or more numbers are relatively prime if they have no common divisor > 1. A single number is not considered to be relatively prime unless it is equal to 1.

Examples

			The a(5) = 13 set partitions:
  {{1},{2,3},{4,5}}
  {{1},{2,5},{3,4}}
   {{1},{2,3,4,5}}
   {{1,2},{3,4,5}}
   {{1,3},{2,4,5}}
   {{1,4},{2,3,5}}
   {{1,5},{2,3,4}}
   {{1,2,3},{4,5}}
   {{1,2,4},{3,5}}
   {{1,2,5},{3,4}}
   {{1,3,4},{2,5}}
   {{1,4,5},{2,3}}
    {{1,2,3,4,5}}
For example, {{1},{2,5},{3,4}} belongs to the list because {1} is relatively prime, {2,5} is relatively prime, and {3,4} is relatively prime. On the other hand, {{1},{2,4},{3,5}} is missing from the list because {2,4} is not relatively prime.
		

Crossrefs

Cf. A000110, A000258, A000837, A008277, A085945, A289508, A289509, A300486, A303139, A320423, A320430.

Programs

Mathematica

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],And@@(GCD@@#==1&/@#)&]],{n,10}]

PARI

lista(nn) = my(m, t=Mat([[], 1]), v, w, z); print1(1); for(n=1, nn, m=Map(); for(i=1, #t~, v=t[i, 1]; if(n-2+sum(j=1, #v, v[j]>1)Jinyuan Wang, Mar 02 2025

Extensions

a(13)-a(23) from Alois P. Heinz, Jan 08 2019

a(24)-a(26) from Jinyuan Wang, Mar 02 2025