Combination with Repetition

combinatorics

Definition

Combination with Repetition

A combination with repetition chooses $k$ elements from $n$ available elements without placing them in order. Order does not matter, and the same element may be chosen more than once. Thus choosing $a,a,b$ gives the same combination as choosing $b,a,a$.

For a finite set $X=\{x_1,\dots ,x_n\}$, such a combination is a multiset of size $k$. It is determined by the multiplicities

$$(m_1,\dots ,m_n),m_i\ge 0,m_1+\cdots +m_n=k,$$

where $m_i$ records how many copies of $x_i$ were chosen. The number of combinations with repetition is

$$C_{\mathrm{rep}}(n,k)=\left(\genfrac{}{}{0ex}{}{n+k-1}{k}\right)=\left(\genfrac{}{}{0ex}{}{n+k-1}{n-1}\right).$$

The construction can be pictured as filling $k$ slots, one selection at a time. At every selection all $n$ elements remain available, so an earlier choice never removes anything. Once the last slot is filled, the order of the slots is discarded and only the multiplicities remain:

Derivation by Stars and Bars

Let $n$ be the number of available element types and let $k$ be the total number of selected occurrences. Represent each of the $k$ selections by a star and separate the $n$ element types with $n-1$ bars. The number of stars in compartment $i$ is the multiplicity $m_i$ of the $i$-th element type.

Reading an ordinary encoding

Fix the element order $a,b,c$. Read the compartments from left to right: stars before the first bar count copies of $a$, stars between the bars count copies of $b$, and stars after the second bar count copies of $c$.

$$\star \star \mid \star \mid \star \star ⟷(m_a,m_b,m_c)=(2,1,2).$$

Hence the encoding represents the selection $\{\{a,a,b,c,c\}\}$.

A bar at an end means a missing type

For the element order $a,b,c$, consider

$$\mid \star \star \star \mid \star ⟷(m_a,m_b,m_c)=(0,3,1).$$

No star appears before the first bar, so $a$ is selected zero times. The three middle stars select three copies of $b$, and the final star selects one copy of $c$. The represented selection is $\{\{b,b,b,c\}\}$.

Adjacent bars mean an empty compartment

For the element order $a,b,c,d$, consider

$$\star \mid \mid \star \star \mid ⟷(m_a,m_b,m_c,m_d)=(1,0,2,0).$$

The adjacent bars leave no star in the $b$-compartment, so $b$ is absent. The final bar leaves no star in the $d$-compartment, so $d$ is absent as well. The represented selection is $\{\{a,c,c\}\}$.

For $n=2$ element types $\{a,b\}$ and $k=3$ selections, there is one bar among four symbol positions. Each path chooses its position and thereby fixes one combination:

Stars to the left of the bar count copies of $a$; stars to its right count copies of $b$. The four paths are exactly the four combinations with repetition.

Every combination with repetition produces exactly one such string, and every such string determines exactly one multiplicity vector. The string contains

$$k+(n-1)=n+k-1$$

symbols. Choosing which $k$ positions contain stars—equivalently, which $n-1$ positions contain bars—gives

$$C_{\mathrm{rep}}(n,k)=\left(\genfrac{}{}{0ex}{}{n+k-1}{k}\right)=\left(\genfrac{}{}{0ex}{}{n+k-1}{n-1}\right).$$

Adjacent bars, or a bar at either end, represent an element chosen zero times, so zero multiplicities are included automatically.

Distinction from Variation with Repetition

Warning

A variation with repetition records an ordered tuple, so $aab$, $aba$, and $baa$ are different. A combination with repetition records only multiplicities, so all three have the same multiplicity vector $(2,1)$ and represent one combination.

Boundary Cases

For $k=0$, there is one empty multiset. For $n=1$, there is one combination for every $k$: choose the sole element $k$ times.

$$C_{\mathrm{rep}}(n,0)=1,C_{\mathrm{rep}}(1,k)=1.$$

Unlike combinations without repetition, $k$ may exceed $n$.

Example

Choosing four scoops

Suppose four scoops of ice cream are chosen from three flavours, with repeated flavours allowed and scoop order ignored. The number of flavour combinations is

$$C_{\mathrm{rep}}(3,4)=\left(\genfrac{}{}{0ex}{}{3+4-1}{4}\right)=\left(\genfrac{}{}{0ex}{}{6}{4}\right)=15.$$