A000743 -id:A000743 - cp's OEIS frontend

A023023 Number of partitions of n into 3 unordered relatively prime parts.

1, 1, 2, 2, 4, 4, 6, 6, 10, 8, 14, 12, 16, 16, 24, 18, 30, 24, 32, 30, 44, 32, 50, 42, 54, 48, 70, 48, 80, 64, 80, 72, 96, 72, 114, 90, 112, 96, 140, 96, 154, 120, 144, 132, 184, 128, 196, 150, 192, 168, 234, 162, 240, 192, 240, 210, 290, 192, 310, 240, 288, 256, 336, 240, 374

Offset: 3

David W. Wilson

nonn

			From _Gus Wiseman_, Oct 08 2020: (Start)
The a(3) = 1 through a(13) = 14 triples (A = 10, B = 11):
  111   211   221   321   322   332   432   433   443   543   544
              311   411   331   431   441   532   533   552   553
                          421   521   522   541   542   651   643
                          511   611   531   631   551   732   652
                                      621   721   632   741   661
                                      711   811   641   831   733
                                                  722   921   742
                                                  731   A11   751
                                                  821         832
                                                  911         841
                                                              922
                                                              931
                                                              A21
                                                              B11
(End)

Fausto A. C. Cariboni, Table of n, a(n) for n = 3..10000
Mohamed El Bachraoui, Relatively Prime Partitions with Two and Three Parts, Fibonacci Quart. 46/47 (2008/2009), no. 4, 341-345.

Cf. A023024-A023030, A000742-A000743, A023032-A023035.
A000741 is the ordered version.
A000837 counts these partitions of any length.
A001399(n-3) does not require relative primality.
A023022 is the 2-part version.
A101271 is the strict case.
A284825 counts the case that is also pairwise non-coprime.
A289509 intersected with A014612 gives the Heinz numbers.
A307719 is the pairwise coprime instead of relatively prime version.
A337599 is the pairwise non-coprime instead of relative prime version.
A008284 counts partitions by sum and length.
A078374 counts relatively prime strict partitions.
A337601 counts 3-part partitions whose distinct parts are pairwise coprime.
Cf. A000010, A000217, A007434, A055684, A078374, A200976, A220377, A302698, A327516, A337563, A337600, A337605.

Table[Length[Select[IntegerPartitions[n,{3}],GCD@@#==1&]],{n,3,50}] (* Gus Wiseman, Oct 08 2020 *)

G.f. for the number of partitions of n into m unordered relatively prime parts is Sum(moebius(k)*x^(m*k)/Product(1-x^(i*k), i=1..m), k=1..infinity). - Vladeta Jovovic, Dec 21 2004
a(n) = (n^2/12)*Product_{prime p|n} (1 - 1/p^2) = A007434(n)/12 for n > 3 (proved by Mohamed El Bachraoui). [Jonathan Sondow, May 27 2009]
a(n) = Sum_{k=1..floor(n/3)} Sum_{i=k..floor((n-k)/2)} floor(1/gcd(i,k,n-i-k)). - Wesley Ivan Hurt, Jan 02 2021

A101271 Number of partitions of n into 3 distinct and relatively prime parts.

Original entry on oeis.org

1, 1, 2, 3, 4, 5, 6, 8, 9, 12, 12, 16, 15, 21, 20, 26, 25, 33, 28, 40, 36, 45, 42, 56, 44, 65, 56, 70, 64, 84, 66, 96, 81, 100, 88, 120, 90, 133, 110, 132, 121, 161, 120, 175, 140, 176, 156, 208, 153, 220, 180, 222, 196, 261, 184, 280, 225, 270, 240, 312, 230, 341, 272

Offset: 6

Vladeta Jovovic, Dec 19 2004

The Heinz numbers of these partitions are the intersection of A289509 (relatively prime), A005117 (strict), and A014612 (triple). - Gus Wiseman, Oct 15 2020

			For n=10 we have 4 such partitions: 1+2+7, 1+3+6, 1+4+5 and 2+3+5.
From _Gus Wiseman_, Oct 13 2020: (Start)
The a(6) = 1 through a(18) = 15 triples (A..F = 10..15):
  321  421  431  432  532  542  543  643  653  654  754  764  765
            521  531  541  632  651  652  743  753  763  854  873
                 621  631  641  732  742  752  762  853  863  954
                      721  731  741  751  761  843  871  872  972
                           821  831  832  851  852  943  953  981
                                921  841  932  861  952  962  A53
                                     931  941  942  961  971  A71
                                     A21  A31  951  A51  A43  B43
                                          B21  A32  B32  A52  B52
                                               A41  B41  A61  B61
                                               B31  C31  B42  C51
                                               C21  D21  B51  D32
                                                         C32  D41
                                                         C41  E31
                                                         D31  F21
                                                         E21
(End)

Fausto A. C. Cariboni, Table of n, a(n) for n = 6..10000

Cf. A023024-A023030, A000742-A000743, A023031-A023035.
A000741 is the ordered non-strict version.
A001399(n-6) does not require relative primality.
A023022 counts pairs instead of triples.
A023023 is the not necessarily strict version.
A078374 counts these partitions of any length, with Heinz numbers A302796.
A101271*6 is the ordered version.
A220377 is the pairwise coprime instead of relatively prime version.
A284825 counts the case that is pairwise non-coprime also.
A337605 is the pairwise non-coprime instead of relatively prime version.
A008289 counts strict partitions by sum and length.
A007304 gives the Heinz numbers of 3-part strict partitions.
A307719 counts 3-part pairwise coprime partitions.
A337601 counts 3-part partitions whose distinct parts are pairwise coprime.
Cf. A000010, A000217, A000837, A007360, A014612, A055684, A289509, A332004, A337452, A337563.

m:=3: with(numtheory): g:=sum(mobius(k)*x^(m*(m+1)/2*k)/Product(1-x^(i*k),i=1..m),k=1..20): gser:=series(g,x=0,80): seq(coeff(gser,x^n),n=6..77); # Emeric Deutsch, May 31 2005

Table[Length[Select[IntegerPartitions[n,{3}],UnsameQ@@#&&GCD@@#==1&]],{n,6,50}] (* Gus Wiseman, Oct 13 2020 *)

G.f. for the number of partitions of n into m distinct and relatively prime parts is Sum(moebius(k)*x^(m*(m+1)/2*k)/Product(1-x^(i*k), i=1..m), k=1..infinity).

More terms from Emeric Deutsch, May 31 2005

A000742 Number of compositions of n into 4 ordered relatively prime parts.

Original entry on oeis.org

1, 4, 10, 20, 34, 56, 80, 120, 154, 220, 266, 360, 420, 560, 614, 816, 884, 1120, 1210, 1540, 1572, 2020, 2080, 2544, 2638, 3276, 3200, 4060, 4040, 4840, 4896, 5960, 5710, 7140, 6954, 8216, 8136, 9880, 9244, 11480, 11010, 12824, 12650, 15180, 14024, 17276

Offset: 4

N. J. A. Sloane

nonn

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Marius A. Burtea, Table of n, a(n) for n = 4..10000
H. W. Gould, Binomial coefficients, the bracket function and compositions with relatively prime summands, Fib. Quart. 2(4) (1964), 241-260.
N. J. A. Sloane, Transforms

Cf. A000741, A000743, A023031, A023032, A023033, A023034, A023035.

[&+[MoebiusMu(n div d)*Binomial(d-1, 3):d in Divisors(n)]:n in[4..49]]; // Marius A. Burtea, Feb 08 2020

with(numtheory):
a:= n-> add(mobius(n/d)*binomial(d-1, 3), d=divisors(n)):
seq(a(n), n=4..50);  # Alois P. Heinz, Feb 05 2020

a[n_] := Sum[Boole[Divisible[n, k]] MoebiusMu[n/k] Binomial[k - 1, 3], {k, 1, n}]; Table[a[n], {n, 4, 51}] (* Jean-François Alcover, Feb 11 2016 *)

Möbius transform of C(n-1,3).

G.f.: Sum_{k>=1} mu(k) * x^(4*k) / (1 - x^k)^4. - Ilya Gutkovskiy, Feb 05 2020

Offset changed to 4 by Ilya Gutkovskiy, Feb 05 2020

A023031 Number of compositions of n into 6 ordered relatively prime parts.

Original entry on oeis.org

1, 6, 21, 56, 126, 252, 461, 792, 1281, 2002, 2982, 4368, 6131, 8568, 11502, 15498, 20097, 26334, 33166, 42504, 52338, 65724, 79443, 98280, 116626, 142506, 166908, 201124, 232968, 278250, 317983, 376992, 427329, 501150, 564108, 658008, 732612

Offset: 6

David W. Wilson

nonn

Marius A. Burtea, Table of n, a(n) for n = 6..5000
N. J. A. Sloane, Transforms

Cf. A000741, A000742, A000743, A023032, A023033, A023034, A023035.

[&+[MoebiusMu(n div d)*Binomial(d-1, 5):d in Divisors(n)]:n in[6..42]]; // Marius A. Burtea, Feb 07 2020

with(numtheory):
a:= n-> add(mobius(n/d)*binomial(d-1, 5), d=divisors(n)):
seq(a(n), n=6..50);  # Alois P. Heinz, Feb 05 2020

a[n_]:=DivisorSum[n, Binomial[#-1, 5] MoebiusMu[n/#]&]; Array[a, 37, 6] (* or *) a[n_]:=Sum[Boole[Divisible[n, k]] MoebiusMu[n/k] Binomial[k - 1, 5], {k, 1, n}]; Table[a[n], {n, 6, 45}] (* Vincenzo Librandi, Feb 06 2020 *)

Moebius transform of C(n-1,5).

G.f.: Sum_{k>=1} mu(k) * x^(6*k) / (1 - x^k)^6. - Ilya Gutkovskiy, Feb 05 2020

A023032 Number of compositions of n into 7 ordered relatively prime parts.

Original entry on oeis.org

1, 7, 28, 84, 210, 462, 924, 1715, 3003, 4998, 8008, 12348, 18564, 27048, 38759, 54054, 74613, 100478, 134596, 176176, 230202, 294294, 376740, 471933, 593775, 731276, 905982, 1099560, 1344903, 1610322, 1947792, 2306220, 2759757, 3235484, 3838380

Offset: 7

David W. Wilson

nonn

Marius A. Burtea, Table of n, a(n) for n = 7..5000
N. J. A. Sloane, Transforms

Cf. A000741, A000742, A000743, A023031, A023033, A023034, A023035.

[&+[MoebiusMu(n div d)*Binomial(d-1,6):d in Divisors(n)]:n in[7..41]]; // Marius A. Burtea, Feb 07 2020

with(numtheory):
a:= n-> add(mobius(n/d)*binomial(d-1, 6), d=divisors(n)):
seq(a(n), n=7..50);  # Alois P. Heinz, Feb 05 2020

a[n_]:=DivisorSum[n, Binomial[#-1, 6] MoebiusMu[n/#]&]; Array[a, 37, 7] (* or *) a[n_]:=Sum[Boole[Divisible[n, k]] MoebiusMu[n/k] Binomial[k-1, 6], {k, 1, n}]; Table[a[n], {n, 7, 45}] (* Vincenzo Librandi, Feb 07 2020 *)

Moebius transform of C(n-1,6).

G.f.: Sum_{k>=1} mu(k) * x^(7*k) / (1 - x^k)^7. - Ilya Gutkovskiy, Feb 05 2020

A023035 Number of compositions of n into 10 ordered relatively prime parts.

Original entry on oeis.org

1, 10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620, 92377, 167960, 293920, 497420, 817135, 1307504, 2042755, 3124550, 4686110, 6906900, 10013002, 14307150, 20155070, 28048790, 38555660, 52451256, 70583095, 94143280, 124355000

Offset: 10

David W. Wilson

nonn

Marius A. Burtea, Table of n, a(n) for n = 10..5000
N. J. A. Sloane, Transforms

Cf. A000741, A000742, A000743, A023031, A023032, A023033, A023034.

Cf. A023023, A023024, A023025, A023026, A023027, A023028, A023029, A023030.

[&+[MoebiusMu(n div d)*Binomial(d-1, 9):d in Divisors(n)]:n in[10..42]]; // Marius A. Burtea, Feb 07 2020

with(numtheory):
a:= n-> add(mobius(n/d)*binomial(d-1, 9), d=divisors(n)):
seq(a(n), n=10..50);  # Alois P. Heinz, Feb 05 2020

a[n_]:=Sum[Boole[Divisible[n, k]] MoebiusMu[n/k] Binomial[k -1, 9], {k, 1, n}]; Table[a[n], {n, 10, 45}] (* or *) Table[a[n],{n, 9, 45}] a[n_]:=DivisorSum[n, Binomial[#-1,9] MoebiusMu[n/#]&]; Array[a, 37, 10] (* Vincenzo Librandi, Feb 08 2020 *)

Moebius transform of C(n-1,9).

G.f.: Sum_{k>=1} mu(k) * x^(10*k) / (1 - x^k)^10. - Ilya Gutkovskiy, Feb 05 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

Emeric Deutsch, Jan 26 2005

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.

			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.

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).
T(2n+1,n+1) gives A000984.
Cf. A007359, A008683, A085411, A101268, A289508, A289509, A302697, A332004, A337485, A337563.

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

T(n,k) = Sum_{d|n} binomial(d-1,k-1)*mobius(n/d).

Sum_{k=1..n} k * T(n,k) = A085411(n). - Alois P. Heinz, May 05 2025

Definition clarified by N. J. A. Sloane, Mar 05 2017

Edited by Alois P. Heinz, May 05 2025

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

David W. Wilson

nonn

Marius A. Burtea, Table of n, a(n) for n = 8..5000
N. J. A. Sloane, Transforms

Cf. A000741, A000742, A000743, A023031, A023032, A023034, A023035.

[&+[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 *)

Moebius transform of C(n-1,7).

G.f.: Sum_{k>=1} mu(k) * x^(8*k) / (1 - x^k)^8. - Ilya Gutkovskiy, Feb 05 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

David W. Wilson

nonn

Marius A. Burtea, Table of n, a(n) for n = 9..5000
N. J. A. Sloane, Transforms

Cf. A000741, A000742, A000743, A023031, A023032, A023033, A023035.

[&+[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 *)

Moebius transform of C(n-1,8).

G.f.: Sum_{k>=1} mu(k) * x^(9*k) / (1 - x^k)^9. - Ilya Gutkovskiy, Feb 05 2020

A341912 Number of partitions of n into 5 distinct and relatively prime parts.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 10, 13, 18, 23, 30, 37, 47, 57, 70, 83, 101, 118, 141, 162, 192, 218, 255, 286, 333, 370, 427, 470, 540, 590, 673, 730, 831, 894, 1014, 1085, 1224, 1305, 1469, 1552, 1747, 1841, 2057, 2163, 2418, 2520, 2818, 2933, 3256, 3388, 3765, 3879, 4319, 4452, 4914, 5068

Offset: 15

Ilya Gutkovskiy, Feb 23 2021

nonn

Cf. A000743, A023022, A023025, A078374, A101271, A339672, A340719, A341868, A341870, A341913, A341914.

nmax = 70; CoefficientList[Series[Sum[MoebiusMu[k] x^(15 k)/Product[1 - x^(j k), {j, 1, 5}], {k, 1, nmax}], {x, 0, nmax}], x] // Drop[#, 15] &

G.f.: Sum_{k>=1} mu(k)* x^(15*k) / Product_{j=1..5} (1 - x^(j*k)).

a(n) <= A001401(n-15). - R. J. Mathar, Feb 28 2021

cp's OEIS Frontend

A023023 Number of partitions of n into 3 unordered relatively prime parts.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A101271 Number of partitions of n into 3 distinct and relatively prime parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A000742 Number of compositions of n into 4 ordered relatively prime parts.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions

A023031 Number of compositions of n into 6 ordered relatively prime parts.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A023032 Number of compositions of n into 7 ordered relatively prime parts.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A023035 Number of compositions of n into 10 ordered relatively prime parts.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

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).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple