The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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). 6
 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 (list; table; graph; refs; listen; history; text; internal format)
 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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 20 06:59 EDT 2021. Contains 343125 sequences. (Running on oeis4.)