A258289 Number of partitions of 1, 2, 3, or more copies of n into distinct parts.

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

Links

Table of n, a(n) for n=0..37.

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

Cf. A000009, A065033, A258280.

Sequence in context: A237666 A285187 A034411 * A066983 A048240 A122012

Adjacent sequences: A258286 A258287 A258288 * A258290 A258291 A258292

Keyword

nonn

Author

Alois P. Heinz, May 25 2015

Status

approved