# What is the number of arrangements in the word “EDUCATION” where vowels are never together?

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

• 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. – NoChance Nov 10 '18 at 11:11

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.

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