login
Number of integer partitions of n whose number of submultisets is less than n.
12

%I #12 May 12 2021 06:44:18

%S 0,0,0,1,2,3,5,7,9,14,20,21,27,43,50,56,69,98,118,143,165,200,229,249,

%T 282,454,507,555,637,706,789,889,986,1406,1567,1690,1875,2396,2602,

%U 2841,3078,3672,3977,4344,4660,5079,5488,5840,6296,10424,11306

%N Number of integer partitions of n whose number of submultisets is less than n.

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

%C The Heinz numbers of these partitions are given by A325797.

%H Alois P. Heinz, <a href="/A325833/b325833.txt">Table of n, a(n) for n = 0..500</a>

%F a(n) = A000041(n) - A325832(n).

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

%e The a(3) = 1 through a(9) = 14 partitions:

%e (3) (4) (5) (6) (7) (8) (9)

%e (22) (32) (33) (43) (44) (54)

%e (41) (42) (52) (53) (63)

%e (51) (61) (62) (72)

%e (222) (322) (71) (81)

%e (331) (332) (333)

%e (511) (422) (432)

%e (611) (441)

%e (2222) (522)

%e (531)

%e (621)

%e (711)

%e (3222)

%e (6111)

%p b:= proc(n, i, p) option remember; `if`(n=0 or i=1,

%p `if`(n=p-1, 1, 0), add(`if`(irem(p, j+1, 'r')=0,

%p (w-> b(w, min(w, i-1), r))(n-i*j), 0), j=0..n/i))

%p end:

%p a:= n-> add(b(n$2, k), k=0..n-1):

%p seq(a(n), n=0..55); # _Alois P. Heinz_, Aug 17 2019

%t Table[Length[Select[IntegerPartitions[n],Times@@(1+Length/@Split[#])<n&]],{n,0,30}]

%t (* Second program: *)

%t b[n_, i_, p_] := b[n, i, p] = If[n == 0 || i == 1,

%t If[n == p - 1, 1, 0], Sum[If[Mod[p, j + 1] == 0, r = p/(j + 1);

%t Function[w, b[w, Min[w, i - 1], r]][n - i*j], 0], {j, 0, n/i}]];

%t a[n_] := Sum[b[n, n, k], {k, 0, n - 1}];

%t a /@ Range[0, 55] (* _Jean-François Alcover_, May 12 2021, after _Alois P. Heinz_ *)

%Y Cf. A002033, A088880, A088881, A098859, A108917, A307699, A325694, A325792, A325797, A325828, A325830, A325831, A325832, A325834, A325836.

%K nonn

%O 0,5

%A _Gus Wiseman_, May 29 2019