Combinations with repetition

Definition

Let $X$ be a set and let $k$ be a natural number. A $k$-combination with repetition of $X$ is a multiset of size $k$ with elements in $X$. That is a function $m : X \to \mathbb{N}$ with $\sum_{x \in X} m(x) = k$, where $m(x)$ is the multiplicity of $x$.

For natural numbers $n$ and $k$, the multiset coefficient $\left(\!\binom{n}{k}\!\right)$ is the number of $k$-combinations with repetition of an $n$-element set.

Remarks

The value is $\left(\!\binom{n}{k}\!\right) = \binom{n + k - 1}{k}$. This is stars and bars. For $X = \{a, b\}$ and $k = 2$ there are $3$ multisets: $\{a, a\}$, $\{a, b\}$ and $\{b, b\}$. Unlike a combination, a combination with repetition can use an element more than once.

Explanations

L1 human

A combination with repetition is a choice of $k$ items from $n$ kinds. You can take the same kind more than once, and the order does not matter. An example is a bag of 3 fruits from apples, pears and plums.