A255906 Number of collections of nonempty multisets with a total of n objects having color set {1,...,k} for some k<=n.

1, 1, 4, 16, 76, 400, 2356, 15200, 106644, 806320, 6526580, 56231024, 513207740, 4941362512, 50013751812, 530481210672, 5880285873060, 67954587978448, 816935340368068, 10196643652651664, 131904973822724540, 1765645473517011568, 24420203895517396180

Offset: 0

Author

Alois P. Heinz, Mar 10 2015

Keywords

• nonn

Comments

Number of multiset partitions of normal multisets of size n, where a multiset is normal if it spans an initial interval of positive integers. - Gus Wiseman, Jul 30 2018

Examples

			a(0) = 1: {}.
a(1) = 1: {{1}}.
a(2) = 4: {{1},{1}}, {{1,1}}, {{1},{2}}, {{1,2}}.
a(3) = 16: {{1},{1},{1}}, {{1},{1,1}}, {{1,1,1}}, {{1},{1},{2}}, {{1},{2},{2}}, {{1},{1,2}}, {{1},{2,2}}, {{2},{1,1}}, {{2},{1,2}}, {{1,1,2}}, {{1,2,2}}, {{1},{2},{3}}, {{1},{2,3}}, {{2},{1,3}}, {{3},{1,2}}, {{1,2,3}}.
		

Links

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

Crossrefs

Row sums of A255903. Also row sums of A317532.

Cf. A007716, A034691, A116539, A317073.

Programs

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_]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Length[Join@@mps/@allnorm[n]],{n,6}] (* Gus Wiseman, Jul 30 2018 *)

PARI

R(n, k)={Vec(-1 + 1/prod(j=1, n, (1 - x^j + O(x*x^n))^binomial(k+j-1, j) ))}
seq(n) = {concat([1], sum(k=1, n, R(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)) ))} \\ Andrew Howroyd, Sep 23 2023

Formula

a(n) = Sum_{k=0..n} A255903(n,k).