Discrete Math Home
Home Courses News Videos Contact
☰

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\).

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