A023034 -id:A023034 - cp's OEIS frontend

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

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

A000743 Number of compositions of n into 5 ordered relatively prime parts.

Original entry on oeis.org

1, 5, 15, 35, 70, 125, 210, 325, 495, 700, 1000, 1330, 1820, 2305, 3060, 3750, 4830, 5775, 7315, 8490, 10625, 12155, 14880, 16835, 20475, 22620, 27405, 30100, 35750, 39100, 46360, 49655, 58905, 62985, 73320, 78340, 91390, 95720, 111930, 117425

Offset: 5

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 = 5..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, A000742, A023031, A023032, A023033, A023034, A023035.

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

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

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

Möbius transform of binomial(n-1, 4).

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

Offset changed to 5 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

A341913 Number of partitions of n into 9 distinct and relatively prime parts.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 41, 54, 73, 94, 123, 157, 201, 252, 318, 393, 488, 598, 732, 887, 1076, 1291, 1549, 1845, 2194, 2592, 3060, 3589, 4206, 4904, 5708, 6615, 7657, 8824, 10156, 11648, 13338, 15224, 17354, 19720, 22380, 25330, 28629, 32277, 36347, 40829, 45812, 51291, 57358

Offset: 45

Ilya Gutkovskiy, Feb 23 2021

nonn

Cf. A023022, A023029, A023034, A078374, A101271, A339672, A340719, A341868, A341870, A341912, A341914.

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

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

cp's OEIS Frontend

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions

A000743 Number of compositions of n into 5 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

Mathematica

PARI

Formula

Extensions

A023033 Number of compositions of n into 8 ordered relatively prime parts.

Views

Author

Keywords

Links

Crossrefs