|
%I #27 Oct 21 2020 22:47:13
%S 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,
%T 56,70,56,28,8,1,4,30,80,125,126,84,36,9,1,10,45,120,210,252,210,120,
%U 45,10,1,4,42,154,325,461,462,330,165,55,11,1,12,66,220,495,792,924,792
%N 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).
%C 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.
%H H. W. Gould, <a href="http://www.fq.math.ca/Scanned/2-4/gould.pdf">Binomial coefficients, the bracket function and compositions with relatively prime summands</a>, Fib. Quart. 2(4) (1964), 241-260.
%H Temba Shonhiwa, <a href="http://www.fq.math.ca/Papers1/44-4/quarttemba04_2006.pdf">Compositions with pairwise relatively prime summands within a restricted setting</a>, Fibonacci Quart. 44 (2006), no. 4, 316-323.
%F T(n, k) = Sum_{d|n}(binomial(d-1, k-1)*mobius(n/d).
%e T(6,3)=9 because we have 411,141,114 and the six permutations of 123 (222 does not qualify).
%e 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.
%e Triangle begins:
%e 1,
%e 2, 1,
%e 2, 3, 1,
%e 4, 6, 4, 1,
%e 2, 9, 10, 5, 1,
%e 6, 15, 20, 15, 6, 1,
%e 4, 18, 34, 35, 21, 7, 1,
%e 6, 27, 56, 70, 56, 28, 8, 1,
%e 4, 30, 80, 125, 126, 84, 36, 9, 1,
%e 10, 45, 120, 210, 252, 210, 120, 45, 10, 1,
%e 4, 42, 154, 325, 461, 462, 330, 165, 55, 11, 1,
%e 12, 66, 220, 495, 792, 924, 792. ...
%e ...
%e From _Gus Wiseman_, Oct 19 2020: (Start)
%e Row n = 6 counts the following compositions:
%e (15) (114) (1113) (11112) (111111)
%e (51) (123) (1122) (11121)
%e (132) (1131) (11211)
%e (141) (1212) (12111)
%e (213) (1221) (21111)
%e (231) (1311)
%e (312) (2112)
%e (321) (2121)
%e (411) (2211)
%e (3111)
%e Missing are: (42), (24), (33), (222).
%e (End)
%p 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
%t 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 *)
%t 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 *)
%o (PARI) T(n, k) = sumdiv(n, d, binomial(d-1, k-1)*moebius(n/d)); \\ _Michel Marcus_, Mar 09 2016
%Y Mirror image of A039911.
%Y Row sums are A000740.
%Y Columns 2-9 are: A000010, A000741, A000742, A000743, A023031, A023032, A023033, A023034.
%Y A000837 counts relatively prime partitions.
%Y A135278 counts compositions by length.
%Y A282748 is the pairwise coprime instead of relatively prime version.
%Y A282750 is the unordered version.
%Y A291166 ranks these compositions (evidently).
%Y Cf. A007359, A101268, A289508, A289509, A302697, A332004, A337485, A337563.
%K nonn,tabl
%O 2,2
%A _Emeric Deutsch_, Jan 26 2005
%E Definition clarified by _N. J. A. Sloane_, Mar 05 2017
|
