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
A023033
Number of compositions of n into 8 ordered relatively prime parts.
Original entry on oeis.org
1, 8, 36, 120, 330, 792, 1716, 3432, 6434, 11440, 19440, 31824, 50352, 77520, 116160, 170544, 244826, 346104, 479908, 657792, 886314, 1184040, 1557312, 2035800, 2623140, 3365736, 4260608, 5379616, 6704742, 8347680, 10263648, 12619464
Offset: 8
-
[&+[MoebiusMu(n div d)*Binomial(d-1,7):d in Divisors(n)]:n in[8..40]]; // Marius A. Burtea, Feb 07 2020
-
with(numtheory):
a:= n-> add(mobius(n/d)*binomial(d-1, 7), d=divisors(n)):
seq(a(n), n=8..50); # Alois P. Heinz, Feb 05 2020
-
a[n_]:=DivisorSum[n, Binomial[# - 1, 7] MoebiusMu[n/#]&]; Array[a, 37, 8] (* or *) a[n_]:=Sum[Boole[Divisible[n, k]] MoebiusMu[n/k] Binomial[k - 1, 7], {k, 1, n}]; Table[a[n], {n, 8, 45}] (* Vincenzo Librandi, Feb 07 2020 *)
A023034
Number of compositions of n into 9 ordered relatively prime parts.
Original entry on oeis.org
1, 9, 45, 165, 495, 1287, 3003, 6435, 12870, 24309, 43758, 75573, 125970, 203445, 319770, 490149, 735471, 1081080, 1562274, 2218788, 3108105, 4289133, 5852925, 7882290, 10518255, 13871286, 18156204, 23511345, 30260340, 38564262, 48902997
Offset: 9
-
[&+[MoebiusMu(n div d)*Binomial(d-1,8):d in Divisors(n)]:n in[9..39]]; // Marius A. Burtea, Feb 07 2020
-
with(numtheory):
a:= n-> add(mobius(n/d)*binomial(d-1, 8), d=divisors(n)):
seq(a(n), n=9..50); # Alois P. Heinz, Feb 05 2020
-
Table[a[n],{n,9,45}]a[n_]:=DivisorSum[n, Binomial[#-1, 8] MoebiusMu[n/#]&]; Array[a, 37, 9] (* or *) a[n_]:=Sum[Boole[Divisible[n,k]] MoebiusMu[n/k] Binomial[k-1,8],{k,1,n}];Table[a[n],{n,9,45}] (* Vincenzo Librandi, Feb 08 2020 *)
A048240
Number of new colors that can be mixed with n units of yellow, blue, red.
Original entry on oeis.org
1, 3, 3, 7, 9, 18, 15, 33, 30, 45, 42, 75, 54, 102, 81, 108, 108, 168, 117, 207, 156, 210, 195, 297, 204, 330, 270, 351, 306, 462, 300, 525, 408, 510, 456, 612, 450, 738, 567, 708, 600, 900, 594, 987, 750, 900, 825, 1173, 792, 1239, 930, 1200
Offset: 0
-
A048240 := proc(n) local ans, i, j, k; ans := 0; for i from n by -1 to 0 do for j from n by -1 to 0 do k := n - i - j; if 0 <= k and k <= n and gcd(gcd(i, j), k) = 1 then ans := ans + 1; fi; od; od; RETURN(ans); end;
-
a[n_] := Sum[ MoebiusMu[n/d]*(d+1)*(d+2)/2, {d, Divisors[n]}]; a[0] = 1; Table[a[n], {n, 0, 51}] (* Jean-François Alcover, Jun 14 2012, after Vladeta Jovovic *)
A015616
Number of triples (i,j,k) with 1 <= i < j < k <= n and gcd(i,j,k) = 1.
Original entry on oeis.org
0, 0, 1, 4, 10, 19, 34, 52, 79, 109, 154, 196, 262, 325, 409, 493, 613, 712, 865, 997, 1171, 1336, 1567, 1747, 2017, 2251, 2548, 2818, 3196, 3472, 3907, 4267, 4717, 5125, 5665, 6079, 6709, 7222, 7858, 8410, 9190, 9748, 10609, 11299, 12127
Offset: 1
For n=6, the a(6) = 19 solutions are the binomial(6,3) = (6*5*4)/(1*2*3) = 20 possible triples minus the triple (2,4,6) with GCD=2.
-
f:=proc(n) local i,j,k,t1,t2,t3; t1:=0; for i from 1 to n-2 do for j from i+1 to n-1 do t2:=gcd(i,j); for k from j+1 to n do t3:=gcd(t2,k); if t3 = 1 then t1:=t1+1; fi; od: od: od: t1; end;
# program based on Moebius transform, partial sums of A000741:
with(numtheory):
b:= proc(n) option remember;
add(mobius(n/d)*(d-2)*(d-1)/2, d=divisors(n))
end:
a:= proc(n) option remember;
b(n) +`if`(n=1, 0, a(n-1))
end:
seq(a(n), n=1..100); # Alois P. Heinz, Feb 08 2011
-
a[n_] := (cnt = 0; Do[cnt += Boole[GCD[i, j, k] == 1], {i, 1, n-2}, {j, i+1, n-1}, {k, j+1, n}]; cnt); Table[a[n], {n, 1, 45}] (* Jean-François Alcover, Mar 05 2013 *)
-
print1(c=0);for(k=1,99,for(j=1,k-1, gcd(j,k)==1 && (c+=j-1) && next; for(i=1,j-1, gcd([i,j,k])>1 || c++)); print1(", "c))
-
from functools import lru_cache
@lru_cache(maxsize=None)
def A015616(n):
if n <= 1:
return 0
c, j = n*(n-1)*(n-2)//6, 2
k1 = n//j
while k1 > 1:
j2 = n//k1 + 1
c -= (j2-j)*A015616(k1)
j, k1 = j2, n//j2
return c # Chai Wah Wu, Mar 30 2021
A338333
Number of relatively prime 3-part strict integer partitions of n with no 1's.
Original entry on oeis.org
0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 4, 4, 7, 6, 10, 8, 14, 12, 18, 16, 24, 18, 30, 25, 34, 30, 44, 31, 52, 42, 56, 49, 69, 50, 80, 64, 83, 70, 102, 71, 114, 90, 112, 100, 140, 98, 153, 117, 153, 132, 184, 128, 195, 154, 196, 169, 234, 156, 252, 196, 241
Offset: 0
The a(9) = 1 through a(19) = 14 triples (A = 10, B = 11, C = 12, D = 13, E = 14):
432 532 542 543 643 653 654 754 764 765 865
632 732 652 743 753 763 854 873 874
742 752 762 853 863 954 964
832 932 843 943 872 972 973
852 952 953 A53 982
942 B32 962 B43 A54
A32 A43 B52 A63
A52 D32 A72
B42 B53
C32 B62
C43
C52
D42
E32
A001399(n-9) does not require relative primality.
A284825 counts the case that is also pairwise non-coprime.
A337452 counts these partitions of any length.
A337563 is the pairwise coprime instead of relatively prime version.
A337605 is the pairwise non-coprime instead of relative prime version.
A338332 is the not necessarily strict version.
A000837 counts relatively prime partitions.
A008284 counts partitions by sum and length.
A078374 counts relatively prime strict partitions.
A101271 counts 3-part relatively prime strict partitions.
A220377 counts 3-part pairwise coprime strict partitions.
A337601 counts 3-part partitions whose distinct parts are pairwise coprime.
-
Table[Length[Select[IntegerPartitions[n,{3}],UnsameQ@@#&&!MemberQ[#,1]&&GCD@@#==1&]],{n,0,30}]
A338332
Number of relatively prime 3-part integer partitions of n with no 1's.
Original entry on oeis.org
0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 5, 3, 8, 6, 9, 9, 16, 10, 21, 15, 22, 20, 33, 21, 38, 30, 41, 35, 56, 34, 65, 49, 64, 56, 79, 55, 96, 72, 93, 77, 120, 76, 133, 99, 122, 110, 161, 105, 172, 126, 167, 143, 208, 136, 213, 165, 212, 182, 261, 163, 280, 210, 257
Offset: 0
The a(7) = 1 through a(17) = 16 triples (A = 10, B = 11, C = 12, D = 13):
322 332 432 433 443 543 544 554 654 655 665
522 532 533 552 553 653 744 754 755
542 732 643 743 753 763 764
632 652 752 762 772 773
722 733 833 843 853 854
742 932 852 943 863
832 942 952 872
922 A32 A33 944
B22 B32 953
962
A43
A52
B33
B42
C32
D22
A001399(n-6) does not require relative primality.
A284825 counts the case that is also pairwise non-coprime.
A302698 counts these partitions of any length.
A337563 is the pairwise coprime instead of relatively prime version.
A008284 counts partitions by sum and length.
Cf.
A000010,
A000741,
A023022,
A078374,
A082024,
A101271,
A307719,
A337450,
A337599,
A337600,
A337601.
-
Table[Length[Select[IntegerPartitions[n,{3}],!MemberQ[#,1]&&GCD@@#==1&]],{n,0,30}]
A344574
Number of ordered pairs (i,j) with 0 < i < j < n such that gcd(i,j,n) > 1.
Original entry on oeis.org
0, 0, 0, 0, 0, 1, 0, 3, 1, 6, 0, 13, 0, 15, 7, 21, 0, 37, 0, 39, 16, 45, 0, 73, 6, 66, 28, 81, 0, 130, 0, 105, 46, 120, 21, 181, 0, 153, 67, 189, 0, 262, 0, 213, 118, 231, 0, 337, 15, 306, 121, 303, 0, 433, 51, 369, 154, 378, 0, 583, 0, 435, 217, 465
Offset: 1
a(8) = 3 via (i, j, n) in {(2, 4, 8), (2, 6, 8), (4, 6, 8)} and that's three such tuples. - _David A. Corneth_, Nov 27 2024
-
f:= proc(n) local t,i,g;
t:= 0:
for i from 1 to n-2 do
g:= igcd(i,n);
if g > 1 then t:= t + nops(select(s -> igcd(s,g) > 1, [$i+1..n-1])) fi
od:
t;
end proc:
map(f, [$1..80]); # Robert Israel, Nov 26 2024
-
npairs[n_]:=Module[{k=0},
Do[Do[
If[GCD[i,j,n]>1,k++]
,{i,1,j-1}],{j,2,n-1}];
Return[k]];
Table[npairs[n],{n,1,60}]
-
a(n) = {my(res = 0, d = divisors(factorback(factor(n)[,1]))); for(i = 2, #d, res+= moebius(d[i])*binomial((n-1)\d[i], 2)); -res} \\ David A. Corneth, Nov 27 2024
Comments