A280880 Number T(n,k) of set partitions of [n] into exactly k blocks where sizes of distinct blocks are coprime; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 1, 3, 1, 0, 1, 4, 6, 1, 0, 1, 15, 10, 10, 1, 0, 1, 6, 75, 20, 15, 1, 0, 1, 63, 21, 245, 35, 21, 1, 0, 1, 64, 476, 56, 630, 56, 28, 1, 0, 1, 171, 540, 2100, 126, 1386, 84, 36, 1, 0, 1, 130, 4185, 2640, 6930, 252, 2730, 120, 45, 1

Offset: 0

Author

Alois P. Heinz, Jan 09 2017

Keywords

• nonn
• tabl

Examples

			T(5,1) = 1: 12345.
T(5,2) = 15: 1234|5, 1235|4, 123|45, 1245|3, 124|35, 125|34, 12|345, 1345|2, 134|25, 135|24, 13|245, 145|23, 14|235, 15|234, 1|2345.
T(5,3) = 10: 123|4|5, 124|3|5, 125|3|4, 134|2|5, 135|2|4, 1|234|5, 1|235|4, 145|2|3, 1|245|3, 1|2|345.
T(5,4) = 10: 12|3|4|5, 13|2|4|5, 1|23|4|5, 14|2|3|5, 1|24|3|5, 1|2|34|5, 15|2|3|4, 1|25|3|4, 1|2|35|4, 1|2|3|45.
T(5,5) = 1: 1|2|3|4|5.
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,   1;
  0, 1,   3,    1;
  0, 1,   4,    6,    1;
  0, 1,  15,   10,   10,    1;
  0, 1,   6,   75,   20,   15,    1;
  0, 1,  63,   21,  245,   35,   21,    1;
  0, 1,  64,  476,   56,  630,   56,   28,   1;
  0, 1, 171,  540, 2100,  126, 1386,   84,  36,  1;
  0, 1, 130, 4185, 2640, 6930,  252, 2730, 120, 45, 1;
		

Links

• Alois P. Heinz, Rows n = 0..200, flattened
• Wikipedia, Coprime integers
• Wikipedia, Partition of a set

Crossrefs

Columns k=0-10 give: A000007, A057427, A194924, A280881, A280882, A280883, A280884, A280885, A280886, A280887, A280888.

T(n+k,n) for k=0-4 give: A000012, A000217, A000292, A051880(n-1) if n>0, A000389(n+4).

Row sums give A280275.

T(2n,n) gives A280889.

Programs

Maple

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

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]]]]; T[n_] := Function [p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, n, {}]]; Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jan 20 2017, after Alois P. Heinz *)