A101391 Triangle read by rows: T(n,k) is the number of compositions of n into k parts x_1, x_2, ..., x_k such that gcd(x_1,x_2,...,x_k) = 1 (1<=k<=n).
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
Offset: 1
Examples
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)
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.
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.
Programs
-
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 # second Maple program: 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 *) -
PARI
T(n, k) = sumdiv(n, d, binomial(d-1, k-1)*moebius(n/d)); \\ Michel Marcus, Mar 09 2016
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
Extensions
Definition clarified by N. J. A. Sloane, Mar 05 2017
Edited by Alois P. Heinz, May 05 2025
Comments