|
| |
|
|
A320424
|
|
Number of set partitions of {1,...,n} where each block's elements are relatively prime.
|
|
5
|
|
|
|
1, 1, 1, 2, 4, 13, 31, 140, 480, 2306, 9179, 58209, 249205, 1802970, 9463155, 63813439, 389176317, 3415876088, 20506436732, 195865505549, 1353967583125, 12006363947433, 93067012435816, 1019489483393439
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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}]
|
|
|
CROSSREFS
|
Cf. A000110, A000258, A000837, A008277, A085945, A289508, A289509, A300486, A303139, A320423, A320430.
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
