login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #17 Jan 08 2019 19:06:33

%S 1,1,1,2,4,13,31,140,480,2306,9179,58209,249205,1802970,9463155,

%T 63813439,389176317,3415876088,20506436732,195865505549,1353967583125,

%U 12006363947433,93067012435816,1019489483393439

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

%C 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 The a(5) = 13 set partitions:

%e {{1},{2,3},{4,5}}

%e {{1},{2,5},{3,4}}

%e {{1},{2,3,4,5}}

%e {{1,2},{3,4,5}}

%e {{1,3},{2,4,5}}

%e {{1,4},{2,3,5}}

%e {{1,5},{2,3,4}}

%e {{1,2,3},{4,5}}

%e {{1,2,4},{3,5}}

%e {{1,2,5},{3,4}}

%e {{1,3,4},{2,5}}

%e {{1,4,5},{2,3}}

%e {{1,2,3,4,5}}

%e 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 sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];

%t Table[Length[Select[sps[Range[n]],And@@(GCD@@#==1&/@#)&]],{n,10}]

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

%K nonn,more

%O 0,4

%A _Gus Wiseman_, Jan 08 2019

%E a(13)-a(23) from _Alois P. Heinz_, Jan 08 2019