A304712 Number of integer partitions of n whose parts are all equal or whose distinct parts are pairwise coprime.

1, 1, 2, 3, 5, 7, 10, 14, 19, 25, 32, 43, 54, 70, 86, 105, 130, 162, 196, 240, 286, 339, 405, 485, 573, 674, 790, 922, 1072, 1252, 1456, 1685, 1939, 2226, 2557, 2923, 3349, 3822, 4347, 4931, 5593, 6335, 7170, 8092, 9105, 10233, 11495, 12903, 14458, 16169, 18063

Offset

0,3

Comments

Two parts are coprime if they have no common divisor greater than 1.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..500

Example

The a(6) = 10 partitions whose parts are all equal or whose distinct parts are pairwise coprime are (6), (51), (411), (33), (321), (3111), (222), (2211), (21111), (111111).

Maple

g:= proc(n, i, s) `if`(n=0, 1, `if`(i<1, 0,
      b(n, i, select(x-> x<=i, s))))
    end:
b:= proc(n, i, s) option remember; g(n, i-1, s)+(f->
     `if`(f intersect s={}, add(g(n-i*j, i-1, s union f)
        , j=1..n/i), 0))(numtheory[factorset](i))
    end:
a:= n-> g(n$2, {}):
seq(a(n), n=0..60);  # Alois P. Heinz, May 17 2018

Mathematica

Table[Select[IntegerPartitions[n], Or[SameQ@@#, CoprimeQ@@Union[#]]&]//Length, {n, 20}]
(* Second program: *)
g[n_, i_, s_] := If[n == 0, 1, If[i < 1, 0, b[n, i, Select[s, # <= i &]]]];
b[n_, i_, s_] := b[n, i, s] = g[n, i - 1, s] + Function[f,
     If[f ~Intersection~ s == {}, Sum[g[n - i*j, i - 1, s ~Union~ f],
     {j, 1, n/i}], 0]][FactorInteger[i][[All, 1]]];
a[n_] := g[n, n, {}];
a /@ Range[0, 60] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)

Crossrefs

Cf. A000837, A007359, A018783, A051424, A056239, A078374, A101268, A289508, A289509, A298748, A300486, A302569, A302696, A302698, A302796, A302797, A304709, A304711.

Sequence in context: A306473 A175846 A088585 * A175842 A008581 A172491

Adjacent sequences: A304709 A304710 A304711 * A304713 A304714 A304715

Keyword

nonn

Author

Gus Wiseman, May 17 2018

Status

approved