login
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.
13
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
Wikipedia, Coprime integers
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
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
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Jan 09 2017
STATUS
approved