rsubmultisets

rsubmultisets, short for restricted submultisets, are a combinatorial generalization of multisets with upper bounds on the multiplicities of elements. Let X be a finite set with elements x1, x2, ..., xn, and let each xi occur with a maximum multiplicity mi ≥ 0 in a larger multiset A. An r-submultiset of A is a multiset B determined by counts ki for i = 1,...,n, where 0 ≤ ki ≤ mi for all i and sum(i) ki = r. Equivalently, B is specified by the vector (k1, ..., kn) with these constraints.

Notation and basic examples: If A has multiplicities mi and we fix r, the number of r-submultisets is the number of integer solutions to k1 + ... + kn = r with 0 ≤ ki ≤ mi. When all mi = 1, r-submultisets reduce to r-element subsets of X, and the count is binomial(n, r). If r exceeds the total available multiplicity sum(mi), there are no r-submultisets.

Generating function and counting: The ordinary generating function for the r-submultisets is given by the coefficient of x^r in the product ∏(i=1 to n) (1 + x + x^2 + ... + x^{mi}) = ∏(i=1 to n) (1 − x^{mi+1})/(1 − x). Equivalently, the count can be obtained by inclusion–exclusion:

Number = sum over all subsets S of {1,...,n} of (−1)^{|S|} binomial(r − sum_{i∈S}(mi+1) + n − 1, n − 1), with the binomial term treated as zero when the top is smaller than n−1.

Relation and applications: rsubmultisets are a special case of submultisets with a fixed total size, and they arise in problems of counting selections from multisets with bounded repetition, partition constraints, and generating-function analyses in combinatorics.