Discrete Math Home

## 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