A302698 Number of integer partitions of n into relatively prime parts that are all greater than 1.

0, 0, 0, 0, 1, 0, 3, 2, 5, 4, 13, 7, 23, 18, 32, 33, 65, 50, 104, 92, 148, 153, 252, 226, 376, 376, 544, 570, 846, 821, 1237, 1276, 1736, 1869, 2552, 2643, 3659, 3887, 5067, 5509, 7244, 7672, 10086, 10909, 13756, 15168, 19195, 20735, 26237, 28708, 35418, 39207

Offset

1,7

Comments

Two or more numbers are relatively prime if they have no common divisor other than 1. A single number is not considered relatively prime unless it is equal to 1 (which is impossible in this case).

The Heinz numbers of these partitions are given by A302697.

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Formula

a(n) = A002865(n) - A018783(n).

Example

The a(5) = 1 through a(12) = 7 partitions (empty column indicated by dot):
  (32)  .  (43)   (53)   (54)    (73)    (65)     (75)
           (52)   (332)  (72)    (433)   (74)     (543)
           (322)         (432)   (532)   (83)     (552)
                         (522)   (3322)  (92)     (732)
                         (3222)          (443)    (4332)
                                         (533)    (5322)
                                         (542)    (33222)
                                         (632)
                                         (722)
                                         (3332)
                                         (4322)
                                         (5222)
                                         (32222)

Maple

b:= proc(n, i, g) option remember; `if`(n=0, `if`(g=1, 1, 0),
      `if`(i<2, 0, b(n, i-1, g)+b(n-i, min(n-i, i), igcd(g, i))))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=1..60);  # Alois P. Heinz, Apr 12 2018

Mathematica

Table[Length[Select[IntegerPartitions[n], FreeQ[#, 1]&&GCD@@#===1&]], {n, 30}]
(* Second program: *)
b[n_, i_, g_] := b[n, i, g] = If[n == 0, If[g == 1, 1, 0], If[i < 2, 0, b[n, i - 1, g] + b[n - i, Min[n - i, i], GCD[g, i]]]];
a[n_] := b[n, n, 0];
Array[a, 60] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)

Crossrefs

A000837 is the version allowing 1's.

A002865 does not require relative primality.

A302697 gives the Heinz numbers of these partitions.

A337450 is the ordered version.

A337451 is the ordered strict version.

A337452 is the strict version.

A337485 is the pairwise coprime instead of relatively prime version.

A000740 counts relatively prime compositions.

A078374 counts relatively prime strict partitions.

A212804 counts compositions with no 1's.

A291166 appears to rank relatively prime compositions.

A332004 counts strict relatively prime compositions.

A337561 counts pairwise coprime strict compositions.

A338332 is the case of length 3, with strict case A338333.

Cf. A007359, A018783, A051424, A101268, A289508, A289509, A302568, A337563, A337984, A338468.

Sequence in context: A356067 A164379 A120332 * A205401 A366264 A329544

Adjacent sequences: A302695 A302696 A302697 * A302699 A302700 A302701

Keyword

nonn

Author

Gus Wiseman, Apr 11 2018

Extensions

Extended by Gus Wiseman, Oct 29 2020

Status

approved