A325832 Number of integer partitions of n whose number of submultisets is greater than or equal to n.

1, 1, 2, 2, 3, 4, 6, 8, 13, 16, 22, 35, 50, 58, 85, 120, 162, 199, 267, 347, 462, 592, 773, 1006, 1293, 1504, 1929, 2455, 3081, 3859, 4815, 5953, 7363, 8737, 10743, 13193, 16102, 19241, 23413, 28344, 34260, 40911, 49197, 58917, 70515, 84055, 100070, 118914

Offset

0,3

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

Links

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

Formula

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

For n even, a(n) = A325831(n) + A325830(n/2); for n odd, a(n) = A325831(n).

Example

The a(1) = 1 through a(8) = 13 partitions:
  (1)  (2)   (21)   (31)    (221)    (321)     (421)      (431)
       (11)  (111)  (211)   (311)    (411)     (2221)     (521)
                    (1111)  (2111)   (2211)    (3211)     (3221)
                            (11111)  (3111)    (4111)     (3311)
                                     (21111)   (22111)    (4211)
                                     (111111)  (31111)    (5111)
                                               (211111)   (22211)
                                               (1111111)  (32111)
                                                          (41111)
                                                          (221111)
                                                          (311111)
                                                          (2111111)
                                                          (11111111)

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-> combinat[numbpart](n)-add(b(n$2, k), k=0..n-1):
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], p/(j + 1)]][n - i*j], 0], {j, 0, n/i}]];
a[n_] := PartitionsP[n] - Sum[b[n, n, k], {k, 0, n - 1}];
Table[a[n], {n, 0, 55}] (* Jean-François Alcover, May 16 2021, after Alois P. Heinz *)

Crossrefs

Cf. A002033, A098859, A108917, A126796, A325694, A325792, A325796, A325828, A325830, A325831, A325833, A325834, A325836.

Sequence in context: A173383 A316076 A368746 * A068598 A293165 A321969

Adjacent sequences: A325829 A325830 A325831 * A325833 A325834 A325835

Keyword

nonn

Author

Gus Wiseman, May 25 2019

Status

approved