A317776 Number of strict multiset partitions of normal multisets of size n, where a multiset is normal if it spans an initial interval of positive integers.

1, 1, 3, 13, 59, 313, 1847, 11977, 84483, 642405, 5228987, 45297249, 415582335, 4021374193, 40895428051, 435721370413, 4850551866619, 56282199807401, 679220819360775, 8508809310177481, 110454586096508563, 1483423600240661781, 20581786429087269819

Offset

0,3

Links

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

Example

The a(3) = 13 strict multiset partitions:
  {{1,1,1}}, {{1},{1,1}},
  {{1,2,2}}, {{1},{2,2}}, {{2},{1,2}},
  {{1,1,2}}, {{1},{1,2}}, {{2},{1,1}},
  {{1,2,3}}, {{1},{2,3}}, {{2},{1,3}}, {{3},{1,2}}, {{1},{2},{3}}.

Maple

C:= binomial:
b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      b(n-i*j, min(n-i*j, i-1), k)*C(C(k+i-1, i), j), j=0..n/i)))
    end:
a:= n-> add(add(b(n$2, i)*(-1)^(k-i)*C(k, i), i=0..k), k=0..n):
seq(a(n), n=0..23);  # Alois P. Heinz, Sep 16 2019

Mathematica

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
allnorm[n_Integer]:=Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1];
Table[Length[Select[Join@@mps/@allnorm[n], UnsameQ@@#&]], {n, 9}]
(* Second program: *)
c := Binomial;
b[n_, i_, k_] := b[n, i, k] = If[n==0, 1, If[i<1, 0, Sum[b[n - i*j, Min[n - i*j, i-1], k] c[c[k+i-1, i], j], {j, 0, n/i}]]];
a[n_] := Sum[b[n, n, i] (-1)^(k-i) c[k, i], {k, 0, n}, {i, 0, k}];
a /@ Range[0, 23] (* Jean-François Alcover, Dec 17 2020, after Alois P. Heinz *)

Crossrefs

Cf. A001055, A007716, A045778, A255906, A281116, A317449, A317532, A317583, A317653, A317752, A317757, A317775.

Row sums of A327116.

Sequence in context: A151234 A330799 A367057 * A145942 A331517 A340411

Adjacent sequences: A317773 A317774 A317775 * A317777 A317778 A317779

Keyword

nonn

Author

Gus Wiseman, Aug 06 2018

Extensions

a(0), a(8)-a(22) from Alois P. Heinz, Sep 16 2019

Status

approved