A327781 Number of integer partitions of n whose LCM is less than n.

0, 0, 1, 2, 4, 5, 9, 12, 18, 22, 30, 37, 52, 69, 89, 110, 143, 163, 204, 243, 298, 374, 451, 516, 620, 790, 932, 1064, 1243, 1454, 1699, 2365, 2733, 3071, 3524, 3945, 4526, 5600, 6361, 7111, 8057, 9405, 10621, 12836, 14395, 16066, 18047, 19860, 22143, 25748

Offset: 0

Author

Gus Wiseman, Sep 25 2019

Keywords

• nonn

Examples

			The a(2) = 1 through a(8) = 18 partitions:
  (11)  (21)   (22)    (41)     (33)      (61)       (44)
        (111)  (31)    (221)    (42)      (322)      (62)
               (211)   (311)    (51)      (331)      (71)
               (1111)  (2111)   (222)     (421)      (332)
                       (11111)  (411)     (511)      (422)
                                (2211)    (2221)     (611)
                                (3111)    (3211)     (2222)
                                (21111)   (4111)     (3221)
                                (111111)  (22111)    (3311)
                                          (31111)    (4211)
                                          (211111)   (5111)
                                          (1111111)  (22211)
                                                     (32111)
                                                     (41111)
                                                     (221111)
                                                     (311111)
                                                     (2111111)
                                                     (11111111)
		

Links

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

Crossrefs

The Heinz numbers of these partitions are given by A327776.

Partitions whose LCM is equal to their sum are A074761.

Partitions whose LCM is greater than their sum are A327779.

Cf. A018818, A290103, A316413, A319333, A326842, A327778, A327780.

Programs

Maple

a:= proc(m) option remember; local b; b:=
      proc(n, i, l) option remember; `if`(n=0, 1,
       `if`(i>1, b(n, i-1, l), 0) +(h-> `if`(h0, b(m$2, 1), 0)
    end:
seq(a(n), n=0..70);  # Alois P. Heinz, Oct 10 2019

Mathematica

Table[Length[Select[IntegerPartitions[n],LCM@@#1, b[n, i - 1, l], 0] + Function[h, If[h0, b[m, m, 1], 0]];
a /@ Range[0, 70] (* Jean-François Alcover, May 18 2021, after Alois P. Heinz *)

PARI

b(m,n)={my(d=divisors(m)); polcoef(1/prod(i=1, #d, 1 - x^d[i] + O(x*x^n)), n)}
a(n)={sum(m=1, n-1, b(m, n)*sum(i=1, (n-1)\m, moebius(i)))} \\ Andrew Howroyd, Oct 09 2019