Multiset - Counting Multisets

Counting Multisets

See also: Stars and bars (combinatorics)

The number of multisets of cardinality k, with elements taken from a finite set of cardinality n, is called the multiset coefficient or multiset number. This number is written by some authors as, a notation that is meant to resemble that of binomial coefficients; it is used for instance in (Stanley, 1997), and could be pronounced "n multichoose k" to resemble "n choose k" for . Unlike for binomial coefficients, there is no "multiset theorem" in which multiset coefficients would occur, and they should not be confused with the unrelated multinomial coefficients that occur in the multinomial theorem. The value of multiset coefficients can be given explicitly as

where the last expression expresses it as binomial coefficient; many authors in fact avoid separate notation and just write binomial coefficients. So, the number of such multisets is the same as the number of subsets of cardinality k in a set of cardinality n + k − 1. The analogy with binomial coefficients can be stressed by writing the numerator in the above expression as a rising factorial power

to match the expression of binomial coefficients using a falling factorial power:

There are for example 4 multisets of cardinality 3 with elements taken from the set {1,2} of cardinality 2 (n=2, k=3), namely : {1,1,1}, {1,1,2}, {1,2,2}, {2,2,2}. And there are also 4 subsets of cardinality 3 in the set {1,2,3,4} of cardinality 4 (n+k-1 = 4), namely : {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}.

One simple way to prove the equality of multiset coefficients and binomial coefficients given above, involves representing multisets in the following way. First, consider the notation for multisets that would represent { a, a, a, a, a, a, b, b, c, c, c, d, d, d, d, d, d, d } (6 as, 2 bs, 3 cs, 7 ds) in this form:

This is a multiset of cardinality 18 made of elements of a set of cardinality 4. The number of characters including both dots and vertical lines used in this notation is 18 + 4 − 1. The number of vertical lines is 4 − 1. The number of multisets of cardinality 18 is then the number of ways to arrange the 4 − 1 vertical lines among the 18 + 4 − 1 characters, and is thus the number of subsets of cardinality 4 − 1 in a set of cardinality 18 + 4 − 1. Equivalently, it is the number of ways to arrange the 18 dots among the 18 + 4 − 1 characters, which is the number of subsets of cardinality 18 of a set of cardinality 18 + 4 − 1. This is

so that is the value of the multiset coefficient

One may define a generalized binomial coefficient

in which n is not required to be a nonnegative integer, but may be negative or a non-integer, or a non-real complex number. (If k = 0, then the value of this coefficient is 1 because it is the empty product.) Then the number of multisets of cardinality k in a set of cardinality n is

This fact led Gian-Carlo Rota to ask "Why are negative sets multisets?". He considered that question worthy of the attention of philosophers of mathematics.