A282750 -id:A282750 - cp's OEIS frontend

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

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

A327029 T(n, k) = Sum_{d|n} phi(d) * A008284(n/d, k) for n >= 1, T(0, 0) = 1. Triangle read by rows for 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 3, 1, 1, 0, 4, 3, 1, 1, 0, 5, 2, 2, 1, 1, 0, 6, 6, 4, 2, 1, 1, 0, 7, 3, 4, 3, 2, 1, 1, 0, 8, 8, 6, 6, 3, 2, 1, 1, 0, 9, 6, 9, 6, 5, 3, 2, 1, 1, 0, 10, 11, 10, 10, 8, 5, 3, 2, 1, 1, 0, 11, 5, 10, 11, 10, 7, 5, 3, 2, 1, 1, 0, 12, 17, 19, 19, 14, 12, 7, 5, 3, 2, 1, 1

Offset: 0

Peter Luschny, Aug 24 2019

Dirichlet convolution of phi(n) and A008284(n,k) for n >= 1. - Richard L. Ollerton, May 07 2021

			Triangle starts:
[0] [1]
[1] [0, 1]
[2] [0, 2, 1]
[3] [0, 3, 1, 1]
[4] [0, 4, 3, 1, 1]
[5] [0, 5, 2, 2, 1, 1]
[6] [0, 6, 6, 4, 2, 1, 1]
[7] [0, 7, 3, 4, 3, 2, 1, 1]
[8] [0, 8, 8, 6, 6, 3, 2, 1, 1]
[9] [0, 9, 6, 9, 6, 5, 3, 2, 1, 1]

Alois P. Heinz, Rows n = 0..200, flattened

Cf. A008284, A000010, A078392 (row sums), A282750.
Cf. A000041 (where reversed rows converge to).
T(2n,n) gives A052810.

def DivisorTriangle(f, T, Len, w = None):
    D = [[1]]
    for n in (1..Len-1):
        r = lambda k: [f(d)*T(n//d,k) for d in divisors(n)]
        L = [sum(r(k)) for k in (0..n)]
        if w != None: L = [*map(lambda v: v * w(n), L)]
        D.append(L)
    return D
DivisorTriangle(euler_phi, A008284, 10)

From Richard L. Ollerton, May 07 2021: (Start)
For n >= 1, T(n,k) = Sum_{i=1..n} A008284(gcd(n,i),k).
For n >= 1, T(n,k) = Sum_{i=1..n} A008284(n/gcd(n,i),k)*phi(gcd(n,i))/phi(n/gcd(n,i)). (End)

A023030 Number of partitions of n into 10 unordered relatively prime parts.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 41, 55, 74, 97, 126, 164, 209, 267, 335, 423, 522, 653, 796, 983, 1189, 1455, 1737, 2112, 2504, 3012, 3548, 4242, 4953, 5888, 6837, 8063, 9321, 10936, 12551, 14663, 16763, 19451, 22155, 25608, 29003, 33400, 37707, 43184, 48614

Offset: 10

David W. Wilson

nonn

Column 10 of A282750.

G.f.: Sum_{k>=1} mu(k)*x^(10*k) / Product_{j=1..10} (1 - x^(j*k)). - Ilya Gutkovskiy, Aug 31 2019

A023024 Number of partitions of n into 4 unordered relatively prime parts.

Original entry on oeis.org

1, 1, 2, 3, 4, 6, 8, 11, 12, 18, 20, 26, 29, 39, 39, 54, 54, 69, 73, 94, 89, 119, 118, 144, 145, 185, 169, 225, 215, 259, 258, 317, 291, 378, 357, 423, 410, 511, 457, 588, 547, 639, 626, 764, 679, 861, 792, 933, 896, 1089, 963, 1203, 1112, 1296, 1240, 1495, 1302, 1650

Offset: 4

David W. Wilson

nonn

Index entries for sequences related to partitions

Column 4 of A282750.

Table[Sum[Sum[Sum[KroneckerDelta[GCD[k, j, i, (n - i - j - k)], 1], {i, j,  Floor[(n - j - k)/2]}], {j, k, Floor[(n - k)/3]}], {k, Floor[n/4]}], {n, 4, 80}] (* Wesley Ivan Hurt, Jan 17 2021 *)

G.f.: Sum_{k>=1} mu(k)*x^(4*k) / Product_{j=1..4} (1 - x^(j*k)). - Ilya Gutkovskiy, Aug 31 2019

a(n) = Sum_{k=1..floor(n/4)} Sum_{j=k..floor((n-k)/3)} Sum_{i=j..floor((n-j-k)/2)} [gcd(k,j,i,n-i-j-k) = 1], where [ ] is the Iverson bracket. - Wesley Ivan Hurt, Jan 17 2021

A338553 Number of integer partitions of n that are either constant or relatively prime.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 10, 15, 20, 29, 37, 56, 68, 101, 122, 170, 213, 297, 352, 490, 587, 778, 948, 1255, 1488, 1953, 2337, 2983, 3585, 4565, 5393, 6842, 8123, 10088, 12015, 14865, 17534, 21637, 25527, 31085, 36701, 44583, 52262, 63261, 74175, 88936, 104305, 124754

Offset: 0

Gus Wiseman, Nov 03 2020

nonn

The Heinz numbers of these partitions are given by A338555 = A000961 \/ A289509. The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), giving a bijective correspondence between positive integers and integer partitions.

			The a(1) = 1 through a(7) = 15 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)
       (11)  (21)   (22)    (32)     (33)      (43)
             (111)  (31)    (41)     (51)      (52)
                    (211)   (221)    (222)     (61)
                    (1111)  (311)    (321)     (322)
                            (2111)   (411)     (331)
                            (11111)  (2211)    (421)
                                     (3111)    (511)
                                     (21111)   (2221)
                                     (111111)  (3211)
                                               (4111)
                                               (22111)
                                               (31111)
                                               (211111)
                                               (1111111)

A023022(n) + A059841(n) is the 2-part version.
A078374(n) + 1 is the strict case (n > 1).
A338554 counts the complement, with Heinz numbers A338552.
A338555 gives the Heinz numbers of these partitions.
A000005 counts constant partitions, with Heinz numbers A000961.
A000837 counts relatively prime partitions, with Heinz numbers A289509.
A282750 counts relatively prime partitions by sum and length.
Cf. A000010, A007360, A008284, A023023, A051424, A101271, A101391, A302698, A304712, A327516, A337664.

Table[Length[Select[IntegerPartitions[n],SameQ@@#||GCD@@#==1&]],{n,0,30}]

For n > 0, a(n) = A000005(n) + A000837(n) - 1.

A023025 Number of partitions of n into 5 unordered relatively prime parts.

Original entry on oeis.org

1, 1, 2, 3, 5, 6, 10, 12, 18, 21, 29, 34, 47, 51, 70, 77, 99, 109, 141, 148, 191, 203, 250, 268, 333, 340, 427, 443, 530, 556, 671, 679, 831, 848, 996, 1028, 1226, 1219, 1469, 1483, 1712, 1757, 2062, 2035, 2416, 2413, 2771, 2813, 3266, 3200, 3754, 3739, 4249

Offset: 5

David W. Wilson

nonn

Column 5 of A282750.

G.f.: Sum_{k>=1} mu(k)*x^(5*k) / Product_{j=1..5} (1 - x^(j*k)). - Ilya Gutkovskiy, Aug 31 2019

A023026 Number of partitions of n into 6 unordered relatively prime parts.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 10, 14, 19, 26, 33, 44, 54, 71, 85, 109, 129, 163, 186, 235, 268, 328, 371, 454, 500, 612, 674, 804, 887, 1056, 1138, 1360, 1469, 1715, 1853, 2172, 2302, 2702, 2873, 3302, 3529, 4070, 4262, 4934, 5187, 5898, 6228, 7104, 7374, 8435, 8799, 9904

Offset: 6

David W. Wilson

nonn

Column 6 of A282750.

G.f.: Sum_{k>=1} mu(k)*x^(6*k) / Product_{j=1..6} (1 - x^(j*k)). - Ilya Gutkovskiy, Aug 31 2019

A023027 Number of partitions of n into 7 unordered relatively prime parts.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 11, 14, 21, 27, 38, 47, 65, 79, 104, 126, 164, 193, 248, 289, 362, 421, 522, 594, 733, 832, 1004, 1137, 1366, 1523, 1824, 2028, 2389, 2655, 3120, 3420, 4011, 4395, 5079, 5567, 6430, 6962, 8032, 8695, 9915, 10744, 12241, 13123, 14945, 16038, 18073

Offset: 7

David W. Wilson

nonn

Column 7 of A282750.

G.f.: Sum_{k>=1} mu(k)*x^(7*k) / Product_{j=1..7} (1 - x^(j*k)). - Ilya Gutkovskiy, Aug 31 2019

A023028 Number of partitions of n into 8 unordered relatively prime parts.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 11, 15, 21, 29, 39, 52, 68, 89, 113, 146, 180, 230, 281, 351, 423, 525, 621, 764, 897, 1087, 1268, 1527, 1756, 2104, 2410, 2850, 3248, 3828, 4317, 5066, 5696, 6614, 7418, 8588, 9542, 11018, 12218, 13983, 15477, 17674, 19414, 22119, 24264

Offset: 8

David W. Wilson

nonn

Column 8 of A282750.

G.f.: Sum_{k>=1} mu(k)*x^(8*k) / Product_{j=1..8} (1 - x^(j*k)). - Ilya Gutkovskiy, Aug 31 2019

A023029 Number of partitions of n into 9 unordered relatively prime parts.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 11, 15, 22, 29, 41, 53, 73, 92, 123, 154, 201, 247, 317, 386, 488, 586, 732, 872, 1074, 1269, 1549, 1812, 2194, 2551, 3055, 3535, 4206, 4824, 5708, 6521, 7645, 8701, 10156, 11476, 13338, 15022, 17332, 19468, 22380, 24984, 28627, 31885, 36306

Offset: 9

David W. Wilson

nonn

Column 9 of A282750.

G.f.: Sum_{k>=1} mu(k)*x^(9*k) / Product_{j=1..9} (1 - x^(j*k)). - Ilya Gutkovskiy, Aug 31 2019

cp's OEIS Frontend

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

A327029 T(n, k) = Sum_{d|n} phi(d) * A008284(n/d, k) for n >= 1, T(0, 0) = 1. Triangle read by rows for 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

SageMath

Formula

A023030 Number of partitions of n into 10 unordered relatively prime parts.

Views

Author

Keywords

Crossrefs

Formula

A023024 Number of partitions of n into 4 unordered relatively prime parts.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A338553 Number of integer partitions of n that are either constant or relatively prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A023025 Number of partitions of n into 5 unordered relatively prime parts.

Views

Author

Keywords

Crossrefs

Formula

A023026 Number of partitions of n into 6 unordered relatively prime parts.

Views

Author

Keywords

Crossrefs

Formula

A023027 Number of partitions of n into 7 unordered relatively prime parts.

Views

Author

Keywords

Crossrefs

Formula

A023028 Number of partitions of n into 8 unordered relatively prime parts.

Views

Author

Keywords

Crossrefs

Formula

A023029 Number of partitions of n into 9 unordered relatively prime parts.

Views

Author

Keywords

Crossrefs