Multiset - Polynomial Notation

Polynomial Notation

The set {x} may be represented by the monomial x. The set of subsets, { {}, {x} }, is represented by the binomial 1 + x.

The set {x,y} may be represented by the monomial x·y. The set of subsets, { {}, {x}, {y}, {x,y} }, is represented by the polynomial

(1 + x)·(1 + y) = 1 + x + y + x·y.

The multiset {x,x} may be represented by the monomial x·x = x2. The multiset of submultisets, { {}, {x}, {x}, {x,x} }, is represented by the polynomial

(1 + x)2 = 1 + x + x + x·x = 1 + 2·x + x2.

The multiset of submultisets of the multiset xn is

That is why the binomial coefficient counts the number of k-combinations of an n-set.

The multiset xK·yN−K, containing N elements, K of which are hits, is called a statistical population, and a submultiset is called a statistical sample. The set of samples is

(1 + x)K·(1 + y)N−K

which by the binomial theorem equals

So the number of n-samples with k hits is

See hypergeometric distribution and inferential statistics for further on the distribution of hits.

The infinite set of finite multisets of elements taken from the set {x}:

{ {}, {x}, {x,x}, {x,x,x}, ... }

may be represented by the formal power series

S = 1 + x + x2 + x3 + ... = 1 + xS .

The formal solution,

S = (1 − x)−1,

makes sense as a set of multisets, but the intermediate result, 1−x, does not make sense as a set of multisets.

The infinite set of finite multisets of elements taken from the set x·y is

(1 − x)−1·(1 − y)−1 = 1 + (x + y) + (x2 + x·y + y2) + ...

The special case y=x : The infinite multiset of finite multisets of elements taken from the multiset x2 is

(1 − x)−2 = 1 + 2·x + 3·x2 + ...

The general case: The infinite multiset of finite multisets of elements taken from the multiset xn is

.

This explains why "multisets are negative sets". The negative binomial coefficients count the number of k-multisets of elements taken from an n-set.