submultisets

Submultisets are a generalization of ordinary subsets to multisets. Given a multiset M on a universe U, a submultiset N of M is another multiset on U such that for every element x in U, the multiplicity of x in N does not exceed the multiplicity of x in M. Equivalently, N can be obtained by removing some occurrences of elements from M. The collection of all submultisets of M forms a partially ordered set under the componentwise order on multiplicities: N ≤ M if and only if for all x in U, the multiplicity of x in N is at most that in M.

A convenient representation of a multiset M is as a function m: U → NonnegativeIntegers, where m(x) is the multiplicity of x in M. Submultisets correspond to functions n: U → NonnegativeIntegers with 0 ≤ n(x) ≤ m(x) for all x. If M has finite multiplicities, say m(x1),…,m(xt) for distinct elements x1,…,xt, then the total number of submultisets is the product ∏(m(xi) + 1). For example, M = {a, a, b} has multiplicities m(a)=2 and m(b)=1, yielding 3×2 = 6 submultisets: ∅, {a}, {a,a}, {b}, {a,b}, and {a,a,b}.

Operations on multisets extend to submultisets via componentwise definitions: the union (in the multiset sense) uses maximum multiplicities, and the intersection uses minimum multiplicities. The submultiset order provides a natural framework in combinatorics and enumeration, where multiplicities play a central role in counting substructures. Submultisets preserve multiplicities up to the limits imposed by M, distinguishing them from ordinary subsets of the underlying set.