Permutation Theorem

Question

I am reading about permutations, and came across this theorem, which has an accompanying proof.

I was wondering if anyone knew of an example, that they could provide, when I would have to use the 2nd equation.

Answer 1

Suppose you have two letter Xes and three letter Ys. How many ways are there to arrange them in a row?

Here we have $n_1=2$ and $n_2=3$, so $n=n_1+n_2 = 5$. The formula says $$\frac{n!}{n_1!n_2!} = \frac{5!}{2!3!} = \frac{120}{2\cdot6} = 10,$$ and indeed:

  XXYYY   (4 arrangements that begin with X)
  XYXYY
  XYYXY
  XYYYX

  YXXYY   (3 arrangements that begin with YX)
  YXYXY
  YXYYX

  YYXXY   (2 arrangements that begin with YYX)
  YYXYX

  YYYXX   (1 arrangement that begins with YYY)

Which is 10; there are no others.

(This is the same as Tom Oldfield's answer, except that he neglected to demonstrate that the answer really is 10 by listing the combinations of apples and oranges, as I have done.)

Answer 2

Take $2$ apples and $3$ oranges. If we claim that all apples look the same as all other apples, and all oranges look the same as all other oranges, then we find that there are $\frac{5!}{(2!)(3!)} = 10$ different permutations of them. The same applies if we take $m$ men and $w$ women, and are unable to tell the men apart from other men or women apart from other women, we would have $\frac{m+n)!}{(m!)(n!)}$ permutations. Note that in the examples, we must be able to tell apples from oranges and men from women.

Answer 3

How many "words" of length $20$ are there, which have $4$ a's, $6$ b's, and $10$ c's?

Answer: $\dfrac{20!}{4!6!10!}$

How many words of length $10$ have $3$ a's, $2$ b's, $2$ c's, and one each of $x$, $y$, and $z$?

Answer: $\dfrac{10!}{3!2!2!1!1!1!}$.

The most important case is the case (in your notation) $c=2$. So the number of words of length $n$, consisting of the letters Y and N, with $n_1$ Y's and $n_2$ N's, where $n_1+n_2=n$, is equal to $\dbinom{n}{n_1! n_2!}$.

Now imagine that we have a group of $n$ people, and we want to choose $n_1$ of them. Or more concretely, we have $52$ cards, and we want to choose $5$ of them. Line up the cards in standard order, and below each one write down a Y (Yes) if you want to choose that card, and N if you don't want that card.

There are exactly as many ways to choose $5$ cards as there are words of length $52$ that have $5$ Y's and $47$ N's. And we know that there are $\dfrac{52!}{5!47!}$ such words.

So the number of ways to choose $5$ cards from $52$, where the order of choice doesn't matter, is $\dfrac{52!}{5!47!}$.

This number is usually called $\dbinom{52}{5!}$, pronounced "$52$ choose $5$." In school it is sometimes called $C(52,5)$, or $C_5^{52}$, or a number of related names.

The binomial coefficient $\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}$ turns up in most branches of mathematics.

Answer 4

How many distinguishable sequences of letters can be made from MISSISSIPPI?

You have one M, four Is, four Ss, and two Ps, so the answer is $$ \frac{11!}{1!\,4\,!\,4!\,2!}. $$