A280275 -id:A280275 - cp's OEIS frontend

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

Alois P. Heinz, Jan 09 2017

			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;

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

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.

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

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

A275313 Number of set partitions of [n] where adjacent blocks differ in size.

Original entry on oeis.org

1, 1, 1, 4, 7, 23, 100, 333, 1443, 6910, 36035, 186958, 1095251, 6620976, 42151463, 290483173, 2030271491, 15044953241, 116044969497, 930056879535, 7749440529803, 66931578540965, 597728811956244, 5511695171795434, 52578231393128128, 515775207055816041

Offset: 0

Alois P. Heinz, Jul 22 2016

nonn

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

Alois P. Heinz, Table of n, a(n) for n = 0..580
Wikipedia, Partition of a set

Cf. A007837, A038041, A275309, A275310, A275311, A275312, A275679, A280275, A286072.

b:= proc(n, i) option remember; `if`(n=0, 1, add(`if`(i=j, 0,
      b(n-j, `if`(j>n-j, 0, j))*binomial(n-1, j-1)), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..35);

b[n_, i_] := b[n, i] = If[n==0, 1, Sum[If[i==j, 0, b[n-j, If[j>n-j, 0, j]]* Binomial[n-1, j-1]], {j, 1, n}]]; a[n_] := b[n, 0]; Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Dec 18 2016, after Alois P. Heinz *)

cp's OEIS Frontend

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica