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

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.

Links

Table of n, a(n) for n=0..26.

Example

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.

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

Prog

(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)<nn, for(j=1, #v, w=v; w[j]=gcd(v[j], n); w=vecsort(w); z=0; mapisdefined(m, w, &z); mapput(m, w, z+t[i, 2])); mapput(m, concat(v, n), t[i, 2]))); print1(", ", sum(i=1, (n+1)\2, mapget(m, vector(i, j, 1)))); t=Mat(m)); \\ Jinyuan Wang, Mar 02 2025

Crossrefs

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

Sequence in context: A148226 A004644 A000866 * A148227 A148228 A148229

Adjacent sequences: A320421 A320422 A320423 * A320425 A320426 A320427

Keyword

nonn,changed

Author

Gus Wiseman, Jan 08 2019

Extensions

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

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

Status

approved