|
|
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, 495, 220, 66, 12, 1
(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
|
|
|
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, 495, 220, 66, 12, 1,
...
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
|
A000837 counts relatively prime partitions.
A135278 counts compositions by length.
A282748 is the pairwise coprime instead of relatively prime version.
A291166 ranks these compositions (evidently).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|