login
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.
10
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
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 *)
KEYWORD
nonn
AUTHOR
Gus Wiseman, Aug 06 2018
EXTENSIONS
a(0), a(8)-a(22) from Alois P. Heinz, Sep 16 2019
STATUS
approved