A282749 -id:A282749 - cp's OEIS frontend

A051424 Number of partitions of n into pairwise relatively prime parts.

1, 1, 2, 3, 4, 6, 7, 10, 12, 15, 18, 23, 27, 33, 38, 43, 51, 60, 70, 81, 92, 102, 116, 134, 153, 171, 191, 211, 236, 266, 301, 335, 367, 399, 442, 485, 542, 598, 649, 704, 771, 849, 936, 1023, 1103, 1185, 1282, 1407, 1535, 1662, 1790, 1917, 2063, 2245, 2436

Offset: 0

Hugo van der Sanden

nonn

			a(4) = 4 since all partitions of 4 consist of relatively prime numbers except 2+2.
The a(6) = 7 partitions with pairwise coprime parts: (111111), (21111), (3111), (321), (411), (51), (6). - _Gus Wiseman_, Apr 14 2018

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..750 (terms 0..400 from Alois P. Heinz)
Eric Schmutz, Partitions whose parts are pairwise relatively prime, Discrete Math. 81(1) (1990), 87-89.
Temba Shonhiwa, Compositions with pairwise relatively prime summands within a restricted setting, Fibonacci Quart. 44(4) (2006), 316-323.

Number of partitions of n into relatively prime parts = A000837.
Row sums of A282749.
Cf. A000837, A007359, A007360, A051424, A289509, A298748, A302569, A302696, A302797.

a051424 = length . filter f . partitions where
   f [] = True
   f (p:ps) = (all (== 1) $ map (gcd p) ps) && f ps
   partitions n = ps 1 n where
     ps x 0 = [[]]
     ps x y = [t:ts | t <- [x..y], ts <- ps t (y - t)]
-- Reinhard Zumkeller, Dec 16 2013

with(numtheory):
b:= proc(n, i, s) option remember; local f;
      if n=0 or i=1 then 1
    elif i<2 then 0
    else f:= factorset(i);
         b(n, i-1, select(x->is(xis(x b(n, n, {}):
seq(a(n), n=0..80);  # Alois P. Heinz, Mar 14 2012

b[n_, i_, s_] := b[n, i, s] = Module[{f}, If[n == 0 || i == 1, 1, If[i < 2, 0, f = FactorInteger[i][[All, 1]]; b[n, i-1, Select[s, # < i &]] + If[i <= n && f ~Intersection~ s == {}, b[n-i, i-1, Select[s ~Union~ f, # < i &]], 0]]]]; a[n_] := b[n, n, {}]; Table[a[n], {n, 0, 54}] (* Jean-François Alcover, Oct 03 2013, translated from Maple, after Alois P. Heinz *)

log a(n) ~ (2*Pi/sqrt(6)) sqrt(n/log n). - Eric M. Schmidt, Jul 04 2013

Apparently no formula or recurrence is known. - N. J. A. Sloane, Mar 05 2017

More precise definition from Vladeta Jovovic, Dec 11 2004

A282750 Triangle read by rows: T(n,k) is the number of partitions of n into k parts x_1, x_2, ..., x_k such that gcd(x_1, x_2, ..., x_k) = 1 (where 1 <= k <= n).

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 2, 2, 1, 1, 0, 1, 2, 2, 1, 1, 0, 3, 4, 3, 2, 1, 1, 0, 2, 4, 4, 3, 2, 1, 1, 0, 3, 6, 6, 5, 3, 2, 1, 1, 0, 2, 6, 8, 6, 5, 3, 2, 1, 1, 0, 5, 10, 11, 10, 7, 5, 3, 2, 1, 1, 0, 2, 8, 12, 12, 10, 7, 5, 3, 2, 1, 1, 0, 6, 14, 18, 18, 14

Offset: 1

N. J. A. Sloane, Mar 05 2017

Columns 2-10 are A023022-A023030. - Lars Blomberg Mar 08 2017

To base the triangle on (0, 0) a column (1, 0, 0, ...) has to be appended to the left hand side of the triangle. To compute this triangle with Michael De Vlieger's Mathematica program only the ranges of the indices have to be adapted. The SageMath program computes the extended triangle by default. - Peter Luschny, Aug 24 2019

			Triangle begins:
   n/k: 1,  2,  3,  4,  5,  6,  7,  8, ...
   1:   1;
   2:   0,  1;
   3:   0,  1,  1;
   4:   0,  1,  1,  1;
   5:   0,  2,  2,  1,  1;
   6:   0,  1,  2,  2,  1,  1;
   7:   0,  3,  4,  3,  2,  1,  1;
   8:   0,  2,  4,  4,  3,  2,  1,  1;
   9:   0,  3,  6,  6,  5,  3,  2,  1,  1;
  10:   0,  2,  6,  8,  6,  5,  3,  2,  1,  1;
  11:   0,  5, 10, 11, 10,  7,  5,  3,  2,  1,  1;
  12:   0,  2,  8, 12, 12, 10,  7,  5,  3,  2,  1,  1;
  ...
The partitions with their gcd value for n=8, k=2..5:
(1, 7)=1, (2, 6)=2, (3, 5)=1, (4, 4)=4, so T(8,2)=2.
(1, 1, 6)=1, (1, 2, 5)=1, (1, 3, 4)=1, (2, 2, 4)=2, (2, 3, 3)=1, so T(8,2)=4.
(1, 1, 1, 5)=1, (1, 1, 2, 4)=1, (1, 1, 3, 3)=1, (1, 2, 2, 3)=1, (2, 2, 2, 2)=2, so T(8,3)=4.
(1, 1, 1, 1, 4)=1, (1, 1, 1, 2, 3)=1, (1, 1, 2, 2, 2)=1, so T(8,4)=3.
(1, 1, 1, 1, 1, 3)=1, (1, 1, 1, 1, 2, 2)=1, so T(8,5)=2.

Michael De Vlieger, Table of n, a(n) for n = 1..5050 (rows 1 <= n <= 100)

Cf. A023022-A023030, A101391 (analog for compositions), A282749 (triangle of partitions into pairwise relatively prime parts).
Row sums = A000837. See also A051424.
For ordinary partition table see A008284.

Table[Length@ Select[IntegerPartitions[n, {k}], GCD @@ # == 1 &], {n, 13}, {k, n}] // Flatten (* Michael De Vlieger, Mar 08 2017 *)

# uses[DivisorTriangle from A327029, A008284]
DivisorTriangle(moebius, A008284, 13) # Peter Luschny, Aug 24 2019

T(n, k) = Sum_{d|n} Moebius(d) * A008284(n/d, k) for n >= 1, T(0, 0) = 1. - Peter Luschny, Aug 24 2019

Corrected a(30)-a(32) and more terms from Lars Blomberg, Mar 08 2017

A282748 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_i, x_j) = 1 for all i != j (where 1 <= k <= n).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 4, 3, 4, 1, 1, 2, 9, 4, 5, 1, 1, 6, 3, 16, 5, 6, 1, 1, 4, 15, 4, 25, 6, 7, 1, 1, 6, 9, 28, 5, 36, 7, 8, 1, 1, 4, 21, 16, 45, 6, 49, 8, 9, 1, 1, 10, 9, 52, 25, 66, 7, 64, 9, 10, 1, 1, 4, 39, 16, 105, 36, 91, 8, 81, 10, 11, 1, 1, 12, 9, 100, 25, 186, 49, 120, 9, 100, 11, 12, 1, 1, 6, 45, 16, 205, 36, 301, 64, 153, 10, 121, 12, 13, 1

Offset: 1

N. J. A. Sloane, Mar 05 2017

See A101391 for the triangle T(n,k) = number of compositions of n into k parts x_1, x_2, ..., x_k such that gcd(x_1,x_2,...,x_k) = 1 (2 <= k <= n).

			Triangle begins:
  1;
  1,  1;
  1,  2,  1;
  1,  2,  3,   1;
  1,  4,  3,   4,   1;
  1,  2,  9,   4,   5,   1;
  1,  6,  3,  16,   5,   6,  1;
  1,  4, 15,   4,  25,   6,  7,   1;
  1,  6,  9,  28,   5,  36,  7,   8,  1;
  1,  4, 21,  16,  45,   6, 49,   8,  9,   1;
  1, 10,  9,  52,  25,  66,  7,  64,  9,  10,  1;
  1,  4, 39,  16, 105,  36, 91,   8, 81,  10, 11,  1;
  1, 12,  9, 100,  25, 186, 49, 120,  9, 100, 11, 12, 1;
  ...
From _Gus Wiseman_, Nov 12 2020: (Start)
Row n = 6 counts the following compositions:
  (6)  (15)  (114)  (1113)  (11112)  (111111)
       (51)  (123)  (1131)  (11121)
             (132)  (1311)  (11211)
             (141)  (3111)  (12111)
             (213)          (21111)
             (231)
             (312)
             (321)
             (411)
(End)

Alois P. Heinz, Rows n = 1..200, flattened (first 100 rows from Chai Wah Wu)
Temba Shonhiwa, Compositions with pairwise relatively prime summands within a restricted setting, Fibonacci Quart. 44 (2006), no. 4, 316-323.

A072704 counts the unimodal instead of coprime version.
A087087 and A335235 rank these compositions.
A101268 gives row sums.
A101391 is the relatively prime instead of pairwise coprime version.
A282749 is the unordered version.
A000740 counts relatively prime compositions, with strict case A332004.
A007360 counts pairwise coprime or singleton strict partitions.
A051424 counts pairwise coprime or singleton partitions, ranked by A302569.
A097805 counts compositions by sum and length.
A178472 counts compositions with a common divisor.
A216652 and A072574 count strict compositions by sum and length.
A305713 counts pairwise coprime strict partitions.
A327516 counts pairwise coprime partitions, ranked by A302696.
A335235 ranks pairwise coprime or singleton compositions.
A337462 counts pairwise coprime compositions, ranked by A333227.
A337562 counts pairwise coprime or singleton strict compositions.
A337665 counts compositions whose distinct parts are pairwise coprime, ranked by A333228.
Cf. A000837, A007359, A302568, A337461, A337561, A337667.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n,{k}],Length[#]==1||CoprimeQ@@#&]],{n,10},{k,n}] (* Gus Wiseman, Nov 12 2020 *)

It seems that no general formula or recurrence is known, although Shonhiwa gives formulas for a few of the early diagonals.

cp's OEIS Frontend

A051424 Number of partitions of n into pairwise relatively prime parts.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A282750 Triangle read by rows: T(n,k) is the number of partitions of n into k parts x_1, x_2, ..., x_k such that gcd(x_1, x_2, ..., x_k) = 1 (where 1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula

Extensions

A282748 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_i, x_j) = 1 for all i != j (where 1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula