A325834 Number of integer partitions of n whose number of submultisets is less than or equal to n.

0, 0, 1, 1, 3, 3, 6, 7, 12, 14, 21, 21, 37, 43, 51, 56, 90, 98, 130, 143, 180, 200, 230, 249, 403, 454, 508, 555, 657, 706, 826, 889, 1295, 1406, 1568, 1690, 2194, 2396, 2603, 2841, 3387, 3672, 4024, 4344, 4693, 5079, 5489, 5840, 9731, 10424, 11336, 12093

Offset: 0

Author

Gus Wiseman, May 29 2019

Keywords

• nonn

Comments

The number of submultisets of a partition is the product of its multiplicities, each plus one.

The Heinz numbers of these partitions are given by A325798.

Examples

			The a(2) = 1 through a(9) = 14 partitions:
  (2)  (3)  (4)   (5)   (6)    (7)    (8)     (9)
            (22)  (32)  (33)   (43)   (44)    (54)
            (31)  (41)  (42)   (52)   (53)    (63)
                        (51)   (61)   (62)    (72)
                        (222)  (322)  (71)    (81)
                        (411)  (331)  (332)   (333)
                               (511)  (422)   (432)
                                      (431)   (441)
                                      (521)   (522)
                                      (611)   (531)
                                      (2222)  (621)
                                      (5111)  (711)
                                              (3222)
                                              (6111)
		

Links

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

Crossrefs

Cf. A002033, A088880, A088881, A108917, A126796, A307699, A325694, A325792, A325798, A325828, A325830, A325831, A325832, A325833, A325836.

Programs

Maple

b:= proc(n, i, p) option remember; `if`(n=0 or i=1,
      `if`(n=p-1, 1, 0), add(`if`(irem(p, j+1, 'r')=0,
      (w-> b(w, min(w, i-1), r))(n-i*j), 0), j=0..n/i))
    end:
a:= n-> add(b(n$2, k), k=0..n):
seq(a(n), n=0..55);  # Alois P. Heinz, Aug 17 2019

Mathematica

Table[Length[Select[IntegerPartitions[n],Times@@(1+Length/@Split[#])<=n&]],{n,0,30}]
(* Second program: *)
b[n_, i_, p_] := b[n, i, p] = If[n == 0 || i == 1, If[n == p - 1, 1, 0], Sum[If[Mod[p, j + 1] == 0, Function[w, b[w, Min[w, i - 1], Quotient[p, j + 1]]][n - i*j], 0], {j, 0, n/i}]];
a[n_] := Sum[b[n, n, k], {k, 0, n}];
a /@ Range[0, 55] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)

Formula

a(n) = A000041(n) - A325831(n).

For n even, A325833(n) = a(n) - A325830(n/2); for n odd, A325833(n) = a(n).