login
A258289
Number of partitions of 1, 2, 3, or more copies of n into distinct parts.
1
1, 1, 1, 3, 3, 7, 9, 17, 21, 43, 57, 109, 157, 301, 447, 895, 1307, 2663, 4207, 8463, 13283, 28489, 45151, 95485, 157767, 336711, 561603, 1236963, 2061173, 4567227, 7946575, 17516101, 30324977, 69519697, 121465499, 276609723, 496333307, 1137900605
OFFSET
0,4
FORMULA
a(n) = Sum_{k=1..A065033(n)} A258280(n,k).
a(n) = Sum_{k=1..max(1,ceiling(n/2))} 1/k! * [Product_{i=1..k} x_i^n] Product_{j>0} (1+Sum_{i=1..k} x_i^j).
EXAMPLE
a(0) = 1: [].
a(1) = 1: [1].
a(2) = 1: [2].
a(3) = 3: [3], [2,1], [3;2,1].
a(4) = 3: [4], [3,1], [4;3,1].
a(5) = 7: [5], [4,1], [3,2], [5;4,1], [5;3,2], [4,1;3,2], [5;4,1;3,2].
a(7) = 17: [7], [6,1], [5,2], [4,3], [4,2,1], [7;6,1], [7;5,2], [7;4,3], [7;4,2,1], [6,1;5,2], [6,1;4,3], [5,2;4,3], [7;6,1;5,2], [7;6,1;4,3], [7;5,2;4,3], [6,1;5,2;4,3], [7;6,1;5,2;4,3].
MAPLE
b:= proc() option remember; local m; m:= args[nargs];
`if`(nargs=1, 1, `if`(args[1]=0, b(args[t] $t=2..nargs),
`if`(m=0 or add(args[i], i=1..nargs-1)> m*(m+1)/2, 0,
b(args[t] $t=1..nargs-1, m-1)+add(`if`(args[j]-m<0, 0,
b(sort([seq(args[i]-`if`(i=j, m, 0), i=1..nargs-1)])[]
, m-1)), j=1..nargs-1))))
end:
a:= n-> add(b(n$k+1)/k!, k=1..max(1, ceil(n/2))):
seq(a(n), n=0..20);
MATHEMATICA
disParts[n_] := disParts[n] = Select[IntegerPartitions[n], Length[#] == Length[Union[#]]&];
T[n_, k_] := Select[Subsets[disParts[n], {k}], Length[Flatten[#]] == Length[Union[Flatten[#]]]&] // Length;
a[n_] := a[n] = If[n == 0, 1, Sum[T[n, k], {k, 1, Quotient[n+1, 2]}]];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 16}] (* Jean-François Alcover, May 01 2022 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, May 25 2015
STATUS
approved