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

Links

Alois P. Heinz, Rows n = 0..200, flattened

Wikipedia, Coprime integers

Wikipedia, Partition of a set

Example

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;

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

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.

Sequence in context: A264435 A356656 A085391 * A050143 A103495 A261699

Adjacent sequences: A280877 A280878 A280879 * A280881 A280882 A280883

Keyword

nonn,tabl

Author

Alois P. Heinz, Jan 09 2017

Status

approved