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

Author

Hugo van der Sanden

Keywords

• nonn

Examples

			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
		

Links

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

Crossrefs

Number of partitions of n into relatively prime parts = A000837.

Row sums of A282749.

Cf. A000837, A007359, A007360, A051424, A289509, A298748, A302569, A302696, A302797.

Programs

Haskell

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

Maple

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

Mathematica

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

Formula

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

Extensions

More precise definition from Vladeta Jovovic, Dec 11 2004