1
$\begingroup$

I know the answer is

$$ 4! P(5,5) $$

Because we can arrange the consonants amongst themselves in 4! ways and then independently insert the five vowels into the five spaces available.

My question is; why the inclusion-exclusion principle is not working?

Since there are nine distinct letters, there are $9!$ total arrangements. The arrangements in which two vowels come together is $$\binom{5}{2}2!8!$$ three vowels come together is $$\binom{5}{3}3!7!$$ four vowels come together is $$\binom{5}{4}4!6!$$ and five vowels come together is $$\binom{5}{5}5!5!$$ But $$ 9!- \binom{5}{2}2!8!+ \binom{5}{3}3!7!- \binom{5}{4}4!6!+ \binom{5}{5}5!5! $$ is not giving the correct answer which is $5!4!$.

Edited: This question has an answer using inclusion exclusion principle where the vowels are three. My question is with five vowels.

$\endgroup$
  • $\begingroup$ There is a duplication in your solution. Notice that when you say "3 vowels come together", this number implicitly INCLUDES or CONTAINS the number of "2 vowels come together". This also applies to "5 Vowels come together" which contains the numbers of 3 and 2, etc. Each step you have listed don't represent an INDEPENDENT count, therefore, we can't manipulate them as such. Try to enumerate each of the counts using a smaller string. $\endgroup$ – NoChance Nov 10 '18 at 11:11
1
$\begingroup$

You have not accounted for those arrangements such as EAUDCTOIN in which there are disjoint pairs of adjacent vowels.

What we need to exclude are adjacent pairs of vowels. Notice that we can partition $5$ in the following ways: \begin{align*} 5 & = 4 + 1\\ & = 3 + 2\\ & = 3 + 1 + 1\\ & = 2 + 2 + 1\\ & = 2 + 1 + 1 + 1\\ & = 1 + 1 + 1 + 1 + 1 \end{align*} Think of these numbers as the number of consecutive vowels.

The case $1 + 1 + 1 + 1 + 1$ in which no two vowels are adjacent is what we want to count.

The case $2 + 1 + 1 + 1$ has one pair of adjacent vowels.

The case $2 + 2 + 1$ has two disjoint pairs of adjacent vowels.

The case $3 + 1 + 1 + 1$ has two overlapping pairs of adjacent vowels (such as the string AEI, which has the pairs AE and EI).

The case $3 + 2$ has three pairs of adjacent vowels, two of which are overlapping.

The case $4 + 1$ has three pairs of adjacent vowels.

The case $5$ has four pairs of adjacent vowels.

We use the Incluson-Exclusion Principle to count the number of admissible choices for the positions of the vowels and consonants first, then arrange the vowels and consonants in the those positions.

There are $\binom{9}{5}$ ways to choose the positions of the vowels. From these, we must exclude those arrangements in which there are one or more pairs of adjacent vowels.

A pair of adjacent vowels: We have eight positions, one for a block of two vowels, three for single vowels, and four for consonants. Choose one position for the block and three of the remaining seven positions for the single vowels. The remaining four positions must be reserved for the four consonants. There are $$\binom{8}{1}\binom{7}{3}$$ such choices.

Two pairs of adjacent vowels: This can occur in two ways. Either there are two overlapping pairs (a block of three consecutive vowels) or two disjoint pairs (two blocks of two vowels each).

Two overlapping pairs: We have seven positions to fill with a block of three vowels, two single vowels, and four consonants. Choose one position for the block and two of the remaining six positions for the single vowels. The remaining four positions must be reserved for the four consonants. There are $$\binom{7}{1}\binom{6}{2}$$ such choices.

Two disjoint pairs: We have seven positions to fill with two blocks of two vowels, one single vowel, and four consonants. Choose two positions for the blocks and one of the remaining five positions for the single vowels. The remaining four positions must be reserved for the four consonants. There are $$\binom{7}{2}\binom{5}{1}$$ such choices.

Three pairs of adjacent vowels: There are again two cases. Either there are three overlapping pairs of adjacent vowels (a block of four consecutive vowels) or two overlapping pairs of vowels (a block of three consecutive vowels) and a disjoint pair of adjacent vowels (a block of two consecutive vowels).

Three overlapping pairs of adjacent vowels: There are six positions to fill with a block of four consecutive vowels, a single vowel, and four consonants. There are six ways to choose the position of the block and five ways to choose the position of the single vowel. The remaining four positions must be reserved for the four consonants. There are $$\binom{6}{1}\binom{5}{1}$$ such choices.

Two overlapping pairs of adjacent vowels and a disjoint pair of adjacent vowels: There are six positions to fill with a block of three consecutive vowels, a block of two consecutive vowels, and four consonants. There are six ways to choose the position of the block of three vowels and five ways to choose the position of the block of two vowels. The remaining four positions must be reserved for the four consonants. There are $$\binom{6}{1}\binom{5}{1}$$ such choices.

Four pairs of adjacent vowels: There are five positions to fill with a block of five consecutive vowels and four consonants. Choose the position of the block. The remaining four positions must be reserved for the four consonants. There are $$\binom{5}{1}$$ such choices.

By the Inclusion-Exclusion Principle, the number of ways of positioning the vowels and consonants so that no two vowels are consecutive is $$\binom{9}{5} - \binom{8}{1}\binom{7}{3} + \binom{7}{1}\binom{6}{2} + \binom{7}{2}\binom{5}{1} - \binom{6}{1}\binom{5}{1} - \binom{6}{1}\binom{5}{1} + \binom{5}{1} = 1$$ namely, VCVCVCVCV.

There are $5!$ ways to arrange the vowels in their five positions and $4!$ ways to arrange the consonants in their four positions. Hence, the number of admissible arrangements is $$\left[\binom{9}{5} - \binom{8}{1}\binom{7}{3} + \binom{7}{1}\binom{6}{2} + \binom{7}{2}\binom{5}{1} - \binom{6}{1}\binom{5}{1} - \binom{6}{1}\binom{5}{1} + \binom{5}{1}\right]5!4! = 5!4!$$ which agrees with your answer.

$\endgroup$
0
$\begingroup$

Since there are five vowels and four consonants, the only possible arrangement scheme is VCVCVCVCV. It follows immediately that the number of arrangements is P(4,4)*P(5,5).

As P(4,4)=4!, this matches your answer key.

Suppose instead we want exactly two vowels to come together. Then we have:

VVCVCVCVC or CVVCVCVCV or VCVVCVCVC or VCVCVVCVC or VCVCVCVVC or their mirror images. Thus, there are P(4,4)*P(5,5)*10=28800 different options. You claim that there are C(5,2)*2!*8!=806400 different options, which is incorrect.

I believe you are talking about at least two vowels being together. Indeed, we can peg two vowels together in eight spots. That leaves seven spots to peg three more vowels. Thus, having at least two vowels together give us 8*C(7,3)*P(5,5)*P(4,4)=806400 options.

$\endgroup$
0
$\begingroup$

Your approach to the problem does not produce the correct result because in the place where you count the arrangements with two vowels together, three vowels together and so on, you are missing a key point that the possible arrangements with two and three vowels together might also contain a third or a fourth vowel together in the word as a whole. For example, you arrange the two chosen vowels V1 and V2 as V1,V2,W,W,W,W,W,W,W where W may be a vowel or a consonant, now you arrange the W s and while arranging them you get this arrangement V1,V2,V3,W,W,W,W,W,W where V3 is a vowel. Now you take the arrangements with three vowels together and in that too you get this arrangement again, so you have double counted. This is the problem. Hope it helps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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