---
tag: 0YEQG3VBYC
kind: definition
name: Combinations with repetition
msc: [05A10]
defines: 0VQQCVG8WA
sources:
  - url: https://en.wikipedia.org/wiki/Multiset
    locator: Counting multisets
---

## 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|009TEMTQKH]].
For $X = \{a, b\}$ and $k = 2$ there are $3$ multisets: $\{a, a\}$, $\{a, b\}$ and $\{b, b\}$.
Unlike a [[combination|0JZSRWRBZE]], 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.