OFFSET
1,5
COMMENTS
If instead we require that the individual parts (x_i,x_j) be relatively prime, we get A282748. This is the question studied by Shonhiwa (2006). - N. J. A. Sloane, Mar 05 2017.
LINKS
Alois P. Heinz, Rows n = 1..200, flattened
H. W. Gould, Binomial coefficients, the bracket function and compositions with relatively prime summands, Fib. Quart. 2(4) (1964), 241-260.
Temba Shonhiwa, Compositions with pairwise relatively prime summands within a restricted setting, Fibonacci Quart. 44 (2006), no. 4, 316-323.
FORMULA
T(n,k) = Sum_{d|n} binomial(d-1,k-1)*mobius(n/d).
Sum_{k=1..n} k * T(n,k) = A085411(n). - Alois P. Heinz, May 05 2025
EXAMPLE
T(6,3)=9 because we have 411,141,114 and the six permutations of 123 (222 does not qualify).
T(8,3)=18 because binomial(0,2)*mobius(8/1)+binomial(1,2)*mobius(8/2)+binomial(3,2)*mobius(8/4)+binomial(7,2)*mobius(8/8)=0+0+(-3)+21=18.
Triangle begins:
1;
0, 1;
0, 2, 1;
0, 2, 3, 1;
0, 4, 6, 4, 1;
0, 2, 9, 10, 5, 1;
0, 6, 15, 20, 15, 6, 1;
0, 4, 18, 34, 35, 21, 7, 1;
0, 6, 27, 56, 70, 56, 28, 8, 1;
0, 4, 30, 80, 125, 126, 84, 36, 9, 1;
0, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1;
0, 4, 42, 154, 325, 461, 462, 330, 165, 55, 11, 1;
0, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1;
...
From Gus Wiseman, Oct 19 2020: (Start)
Row n = 6 counts the following compositions:
(15) (114) (1113) (11112) (111111)
(51) (123) (1122) (11121)
(132) (1131) (11211)
(141) (1212) (12111)
(213) (1221) (21111)
(231) (1311)
(312) (2112)
(321) (2121)
(411) (2211)
(3111)
Missing are: (42), (24), (33), (222).
(End)
MAPLE
with(numtheory): T:=proc(n, k) local d, j, b: d:=divisors(n): for j from 1 to tau(n) do b[j]:=binomial(d[j]-1, k-1)*mobius(n/d[j]) od: sum(b[i], i=1..tau(n)) end: for n from 1 to 14 do seq(T(n, k), k=1..n) od; # yields the sequence in triangular form
# Alternative:
b:= proc(n, g) option remember; `if`(n=0, `if`(g=1, 1, 0),
expand(add(b(n-j, igcd(g, j))*x, j=1..n)))
end:
T:= (n, k)-> coeff(b(n, 0), x, k):
seq(seq(T(n, k), k=1..n), n=1..14); # Alois P. Heinz, May 05 2025
MATHEMATICA
t[n_, k_] := Sum[Binomial[d-1, k-1]*MoebiusMu[n/d], {d, Divisors[n]}]; Table[t[n, k], {n, 2, 14}, {k, 2, n}] // Flatten (* Jean-François Alcover, Jan 20 2014 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n, {k}], GCD@@#==1&]], {n, 10}, {k, 2, n}] (* change {k, 2, n} to {k, 1, n} for the version with zeros. - Gus Wiseman, Oct 19 2020 *)
PROG
(PARI) T(n, k) = sumdiv(n, d, binomial(d-1, k-1)*moebius(n/d)); \\ Michel Marcus, Mar 09 2016
CROSSREFS
Mirror image of A039911.
Row sums are A000740.
A000837 counts relatively prime partitions.
A135278 counts compositions by length.
A282748 is the pairwise coprime instead of relatively prime version.
A282750 is the unordered version.
A291166 ranks these compositions (evidently).
T(2n+1,n+1) gives A000984.
KEYWORD
AUTHOR
Emeric Deutsch, Jan 26 2005
EXTENSIONS
Definition clarified by N. J. A. Sloane, Mar 05 2017
Edited by Alois P. Heinz, May 05 2025
STATUS
approved
