## Generalized Permutations and Combinations |

In this section, we study \(r\)-permutations and \(r\)-combinations of \(n\) types of objects with repetition allowed. For example, consider three types of letters \(a,b\), and \(c\).

- The \(2\)-combinations of \(a,b,c\) with repetition allowed are \[\{a,b\},\;\{a,c\},\;\{b,c\}, \;\{a,a\},\;\{b,b\},\;\{c,c\}.\]
- The \(2\)-permutations of \(a,b,c\) with repetition allowed are \[(a,b),\;(b,a),\;(a,c),\;(c,a),\;(b,c),\;(c,b),\;(a,a),\;(b,b),\;(c,c).\]

**Theorem.**
Let \(n\) and \(r\) be two positive integers. Then the number of \(r\)-permutations of \(n\) types of objects
with repetition allowed is \(n^r\) and the number of \(r\)-combinations of \(n\) types of objects
with repetition allowed is
\[\binom{n+r-1}{r}.\]

(Stars and bars)

**Example.**
How many strings of length \(5\) can be formed from the uppercase letters of the English alphabet?

*Solution.*
The number of \(5\)-permutations of \(26\) types of uppercase letters with repetition allowed is \(26^5\).

**Example.**
How many different ways are there to choose a dozen nuts from the ten varieties at a donut shop?

*Solution.*
The number of ways is the number of \(12\)-combinations of \(10\) types of donuts with repetition
allowed which is
\[\binom{10+12-1}{12}=\binom{21}{12}.\]

**Example.**
Find the number of solutions to the equation
\[x_1+x_2+x_3+x_4=10,\]
where \(x_1,x_2,x_3,x_4\) are nonnegative integers.

*Solution.*
The number of solutions is the number of \(10\)-combinations of \(4\) types of objects with
repetition allowed which is
\[\binom{4+10-1}{10}=\binom{13}{10}=286.\]

**Theorem.**
The number of permutations of \(n\) objects of \(k\) types, where \(n_i\) is the number of object type \(i\)
for \(1,2,\ldots,k\), is
\[\frac{n!}{n_1!n_2!\cdots n_k!}.\]

There are \(\binom{n}{n_1}\) ways to choose type 1 object in \(n_1\) places out of \(n\) ordered places.
After choosing type 1 object, there are \(\binom{n-n_1}{n_2}\) ways to choose type 2 object in \(n_2\) places
from the remaining \(n-n_1\) places. Similarly there are \(\binom{n-n_1-\cdots -n_{k-1}}{n_k}\) ways
to choose type \(k\) object in \(n_k\) places from the remaining \(n-n_1-\cdots -n_{k-1}=n_k\) places.
By the product rule, the number of permutations is
\[\begin{eqnarray*}
&&\binom{n}{n_1}\binom{n-n_1}{n_2}\cdots \binom{n-n_1-\cdots -n_{k-1}}{n_k}\\
&=& \frac{n!}{n_1!(n-n_1)!} \frac{(n-n_1)!}{n_2!(n-n_1-n_2)!} \cdots \frac{(n-n_1-\cdots -n_{k-1})!}{n_k!0!}\\
&=& \frac{n!}{n_1!n_2!\cdots n_k!}.
\end{eqnarray*}\]

**Example.**
How many different strings can be made from the letters in MISSISSIPPI using all the letters?

*Solution.*
There are 11 letters of 4 types: 4 Is, 4 Ss, 2 Ps, and 1 M. Thus the number of different strings is
\[\frac{11!}{4!4!2!1!}=34650.\]
Alternatively, by the product rule, the number of different strings is
\[\binom{11}{4}\binom{7}{4}\binom{3}{2}\binom{1}{1}=34650.\]

Last edited