Multiset — Definition, Formula & Examples

A multiset is a collection of objects where the same element can appear more than once. Unlike an ordinary set, a multiset tracks how many times each element occurs.

A multiset over a ground set $S$ is a pair $(S, m)$ where $m: S \to \mathbb{Z}_{\geq 0}$ is a function assigning a non-negative integer multiplicity to each element of $S$ . The cardinality of the multiset is $\sum_{s \in S} m(s)$ .

Key Formula

\binom{n + k - 1}{k} = \binom{n + k - 1}{n - 1}

Where:

$n$ = Number of distinct element types in the ground set
$k$ = Number of elements chosen (the size of the multiset)

How It Works

In standard set notation,

\{a, a, b\}

simplifies to

\{a, b\}

because sets ignore duplicates. A multiset preserves duplicates, so

\{a, a, b\}

is distinct from

\{a, b\}

. The number of times an element appears is called its multiplicity. Multisets are often written with double braces or square brackets to distinguish them from ordinary sets, though conventions vary by author. In combinatorics, choosing

k

items from

n

types with repetition allowed is equivalent to counting

k

-element multisets drawn from an

n

-element set.

Worked Example

Problem: How many ways can you choose 4 scoops of ice cream from 3 flavors (chocolate, vanilla, strawberry) if you may repeat flavors?

Identify the parameters: There are

n = 3

flavors and you choose

k = 4

scoops with repetition allowed, so you are counting 4-element multisets from a 3-element set.

Apply the multiset coefficient formula: Substitute into the formula for the number of multisets of size

k

from

n

types.

\binom{3 + 4 - 1}{4} = \binom{6}{4}

Compute: Evaluate the binomial coefficient.

\binom{6}{4} = \frac{6!}{4!\,2!} = \frac{720}{24 \cdot 2} = 15

Answer: There are 15 possible multisets, meaning 15 ways to choose 4 scoops from 3 flavors when repetition is allowed.

Why It Matters

Multisets appear whenever you model selections with repetition, such as distributing identical objects into distinct bins or counting monomials of a given degree. The multiset coefficient (also called "stars and bars") is a standard tool in combinatorics and probability courses, and it arises in areas like inventory problems and polynomial algebra.

Common Mistakes

Mistake: Using

\binom{n}{k}

(ordinary combination) when repetition is allowed.

Correction: When elements can repeat, use the multiset coefficient

\binom{n+k-1}{k}

instead. The ordinary combination

\binom{n}{k}

only counts subsets without repetition.