A101268
Number of compositions of n into pairwise relatively prime parts.
Original entry on oeis.org
1, 1, 2, 4, 7, 13, 22, 38, 63, 101, 160, 254, 403, 635, 984, 1492, 2225, 3281, 4814, 7044, 10271, 14889, 21416, 30586, 43401, 61205, 85748, 119296, 164835, 226423, 309664, 422302, 574827, 781237, 1060182, 1436368, 1942589, 2622079, 3531152, 4742316, 6348411
Offset: 0
From _Gus Wiseman_, Oct 18 2020: (Start)
The a(1) = 1 through a(5) = 13 compositions:
(1) (2) (3) (4) (5)
(11) (12) (13) (14)
(21) (31) (23)
(111) (112) (32)
(121) (41)
(211) (113)
(1111) (131)
(311)
(1112)
(1121)
(1211)
(2111)
(11111)
(End)
A337461 counts these compositions of length 3, with unordered version
A307719 and unordered strict version
A220377.
A337462 does not consider a singleton to be coprime unless it is (1), with strict version
A337561.
A337664 looks only at distinct parts, with non-constant version
A337665.
A000740 counts relatively prime compositions, with strict case
A332004.
A178472 counts compositions with a common factor.
-
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[#]<=1||CoprimeQ@@#&]],{n,0,10}] (* Gus Wiseman, Oct 18 2020 *)
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).
Original entry on oeis.org
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
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)
- 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.
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).
-
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
-
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 *)
-
T(n, k) = sumdiv(n, d, binomial(d-1, k-1)*moebius(n/d)); \\ Michel Marcus, Mar 09 2016
Showing 1-2 of 2 results.
Comments