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 (2<=k<=n).

1, 2, 1, 2, 3, 1, 4, 6, 4, 1, 2, 9, 10, 5, 1, 6, 15, 20, 15, 6, 1, 4, 18, 34, 35, 21, 7, 1, 6, 27, 56, 70, 56, 28, 8, 1, 4, 30, 80, 125, 126, 84, 36, 9, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 4, 42, 154, 325, 461, 462, 330, 165, 55, 11, 1, 12, 66, 220, 495, 792, 924, 792

Offset

2,2

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

Table of n, a(n) for n=2..74.

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

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,
   2,  1,
   2,  3,   1,
   4,  6,   4,   1,
   2,  9,  10,   5,   1,
   6, 15,  20,  15,   6,   1,
   4, 18,  34,  35,  21,   7,   1,
   6, 27,  56,  70,  56,  28,   8,   1,
   4, 30,  80, 125, 126,  84,  36,   9,  1,
  10, 45, 120, 210, 252, 210, 120,  45, 10,  1,
   4, 42, 154, 325, 461, 462, 330, 165, 55, 11, 1,
  12, 66, 220, 495, 792, 924, 792. ...
  ...
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 2 to 14 do seq(T(n, k), k=2..n) od; # yields the sequence in triangular form

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.

Columns 2-9 are: A000010, A000741, A000742, A000743, A023031, A023032, A023033, A023034.

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

Cf. A007359, A101268, A289508, A289509, A302697, A332004, A337485, A337563.

Sequence in context: A125930 A210790 A224653 * A327632 A117704 A078032

Adjacent sequences: A101388 A101389 A101390 * A101392 A101393 A101394

Keyword

nonn,tabl

Author

Emeric Deutsch, Jan 26 2005

Extensions

Definition clarified by N. J. A. Sloane, Mar 05 2017

Status

approved