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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..500

Wikipedia, Coprime integers

Wikipedia, Partition of a set

Formula

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

Example

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.

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 *)

Crossrefs

Cf. A000110, A007837, A275313.

Row sums of A280880.

Sequence in context: A267400 A363064 A052302 * A009598 A355861 A002216

Adjacent sequences: A280272 A280273 A280274 * A280276 A280277 A280278

Keyword

nonn

Author

Alois P. Heinz, Dec 30 2016

Status

approved