# Permutation of items with a constant order subset.

• Jul 6th 2011, 09:03 AM
driegert
Permutation of items with a constant order subset.
I just wrote a practice midterm for a probability course. There was no answer key and the person who "marked" the exam and I were unsure about one of the questions.

"What is the probability that in a random permutation of the nine letters A, E, I, O, U, C, F, S, and T, the vowels appear in alphabetic order -- A, E, I, O, U (e.g., as in "FACETIOUS")?"

I ended up with:

\begin{align*}P(A) &= \frac{\binom{4}{1} \cdot 6 \cdot \binom{3}{1} \cdot 7 \cdot \binom{2}{1} \cdot 8 \cdot \binom{1}{1} \cdot 9}{9!} \\ &= \frac{(9 \cdot 8 \cdot 7 \cdot 6) \cdot 4!}{9!} \\ &= 0.2 \end{align*}

My rational being that you order A, E, I, O, U and you have 6 choices of where to put the first of the remaining 4 letters: _ A _ E _ I _ O _ U _ . So, choose one of those letters, $\binom{4}{1}$ and multiply by the 6 possibilities. Once the first letter is placed, it opens up a new spot. Choose the next letter, $\binom{3}{1}$, and place it in one of the 7 remaining spots. (Same for last two remaining letters).

The marker ended up with:

\begin{align*} P(A) &= \frac{\binom{9}{5}4!}{9!} \\ &= \frac{9 \cdot 8 \cdot 7 \cdot 6}{9!} \\ &= 0.0083 \bar{3} \end{align*}

His rational being that you have 9 spots to fill, choose 5 of them for the vowels, and arrange the remaining four letters in the remaining 4 spots.

I ended up with an additional 4!, but neither of us could see where I (most likely) went wrong.

Any clarification you could provide would be greatly appreciated :).

Thanks,
--
Dave

(Hopefully I explained that properly.)
• Jul 6th 2011, 09:28 AM
Re: Permutation of items with a constant order subset.
I would calculate, using the fact that there are $\binom{11}{5}$
ways to have A, E, I, O, U in that order.

For each of these, there are 6! ways to arrange the remaining letters.

Hence, the probability is

$\frac{6!\binom{11}{5}}{11!}=0.008333...$
• Jul 6th 2011, 09:29 AM
emakarov
Re: Permutation of items with a constant order subset.
The marker is right.

Quote:

Originally Posted by driegert
My rational being that you order A, E, I, O, U and you have 6 choices of where to put the first of the remaining 4 letters: _ A _ E _ I _ O _ U _ . So, choose one of those letters, $\binom{4}{1}$ and multiply by the 6 possibilities. Once the first letter is placed, it opens up a new spot. Choose the next letter, $\binom{3}{1}$, and place it in one of the 7 remaining spots. (Same for last two remaining letters).

Suppose at first you chose F and decided to insert it between A and E. Then suppose you chose C and inserted it between F and E. On the other hand, you could choose C first and insert it between A and E, then choose F and insert it between A and C. In both cases, you end up with _ A _F _ C _ E _ I _ O _ U _. Thus, you count several variants twice.
• Jul 6th 2011, 09:31 AM
driegert
Re: Permutation of items with a constant order subset.
Thanks! I was thinking I had double permuted the remaining letters.
• Jul 6th 2011, 09:50 AM
Plato
Re: Permutation of items with a constant order subset.
Quote:

Originally Posted by driegert
"What is the probability that in a random permutation of the nine letters A, E, I, O, U, C, F, S, and T, the vowels appear in alphabetic order -- A, E, I, O, U (e.g., as in "FACETIOUS")?"

There is a simple way to look at this problem.
The answer is simply $\frac{1}{5!}=\frac{1}{120}=0.008\overline{3}$

Look at it this way. Only 1 in every 120 arrangements do the vowels appear in alphabetic order.
It is the same answer if the set were
$\{A,B,C,E,I,K,L,M,N,O,U,X,Y,Z\}$.