A280275 Number of set partitions of [n] where sizes of distinct blocks are coprime.

1, 1, 2, 5, 12, 37, 118, 387, 1312, 4445, 17034, 73339, 342532, 1616721, 7299100, 31195418, 129179184, 578924785, 3057167242, 18723356715, 120613872016, 738703713245, 4080301444740, 20353638923275, 95273007634552, 443132388701107, 2149933834972928

Offset: 0

Author

Alois P. Heinz, Dec 30 2016

Keywords

• nonn

Examples

			a(n) = A000110(n) for n<=3.
a(4) = 12: 1234, 123|4, 124|3, 12|3|4, 134|2, 13|2|4, 1|234, 1|23|4, 14|2|3, 1|24|3, 1|2|34, 1|2|3|4.
a(5) = 37: 12345, 1234|5, 1235|4, 123|45, 123|4|5, 1245|3, 124|35, 124|3|5, 125|34, 12|345, 125|3|4, 12|3|4|5, 1345|2, 134|25, 134|2|5, 135|24, 13|245, 135|2|4, 13|2|4|5, 145|23, 14|235, 15|234, 1|2345, 1|234|5, 1|235|4, 1|23|4|5, 145|2|3, 14|2|3|5, 1|245|3, 1|24|3|5, 1|2|345, 1|2|34|5, 15|2|3|4, 1|25|3|4, 1|2|35|4, 1|2|3|45, 1|2|3|4|5.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..500
• Wikipedia, Coprime integers
• Wikipedia, Partition of a set

Crossrefs

Cf. A000110, A007837, A275313.

Row sums of A280880.

Programs

Maple

with(numtheory):
b:= proc(n, i, s) option remember;
      `if`(n=0 or i=1, 1, b(n, i-1, select(x->x<=i-1, s))+
      `if`(i>n or factorset(i) intersect s<>{}, 0, b(n-i, i-1,
      select(x->x<=i-1, s union factorset(i)))*binomial(n, i)))
    end:
a:= n-> b(n$2, {}):
seq(a(n), n=0..30);

Mathematica

b[n_, i_, s_] := b[n, i, s] = Expand[If[n==0 || i==1, x^n, b[n, i-1, Select[s, # <= i-1&]] + If[i>n || FactorInteger[i][[All, 1]] ~Intersection~ s != {}, 0, x*b[n-i, i-1, Select[s ~Union~ FactorInteger[i][[All, 1]], # <= i-1&]]*Binomial[n, i]]]];
a[n_] := b[n, n, {}] // CoefficientList[#, x]& // Total;
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 23 2017, translated from Maple *)

Formula

a(n) = Sum_{k=0..n} A280880(n,k).