Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

enter image description here

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

share|improve this question
    
The second equation generalizes binomial coefficients. If you think about it, the case $c=2$ are combinations rather than permutations (think of it as dividing out the order of the permutation to get a combination). For $c>2$ we get multinomials instead. –  EuYu Feb 16 '13 at 20:15
add comment

4 Answers

up vote 1 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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!}. $$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.