cp's OEIS Frontend

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

%I A320424 #22 Mar 02 2025 22:54:19
%S A320424 1,1,1,2,4,13,31,140,480,2306,9179,58209,249205,1802970,9463155,
%T A320424 63813439,389176317,3415876088,20506436732,195865505549,1353967583125,
%U A320424 12006363947433,93067012435816,1019489483393439,7779097711766093,86684751695545733,766357409555622203
%N A320424 Number of set partitions of {1,...,n} where each block's elements are relatively prime.
%C A320424 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.
%e A320424 The a(5) = 13 set partitions:
%e A320424   {{1},{2,3},{4,5}}
%e A320424   {{1},{2,5},{3,4}}
%e A320424    {{1},{2,3,4,5}}
%e A320424    {{1,2},{3,4,5}}
%e A320424    {{1,3},{2,4,5}}
%e A320424    {{1,4},{2,3,5}}
%e A320424    {{1,5},{2,3,4}}
%e A320424    {{1,2,3},{4,5}}
%e A320424    {{1,2,4},{3,5}}
%e A320424    {{1,2,5},{3,4}}
%e A320424    {{1,3,4},{2,5}}
%e A320424    {{1,4,5},{2,3}}
%e A320424     {{1,2,3,4,5}}
%e A320424 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.
%t A320424 sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];
%t A320424 Table[Length[Select[sps[Range[n]],And@@(GCD@@#==1&/@#)&]],{n,10}]
%o A320424 (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
%Y A320424 Cf. A000110, A000258, A000837, A008277, A085945, A289508, A289509, A300486, A303139, A320423, A320430.
%K A320424 nonn
%O A320424 0,4
%A A320424 _Gus Wiseman_, Jan 08 2019
%E A320424 a(13)-a(23) from _Alois P. Heinz_, Jan 08 2019
%E A320424 a(24)-a(26) from _Jinyuan Wang_, Mar 02 2025