Arrange INDEPENDENCE such that no vowels occur together.

Question

Find the number of arrangements of the word INDEPENDENCE such that no vowels occur together, I tried to solve this with 2 approaches, however, I am not able to get the answer my textbook gives… I firstly tried to do this by Principle of Inclusion and Exclusion, so total permutations of the word are 12!/(4!*3!*2!), then i subtracted the permutations in which 2 vowels occur together from the total number of permutations, for obtaining the no. of permutations, I tried the box method and kept EI and EE in the box, so there would be 11!/(2!*2!*3!) + (11!*2!)/(3!*3!*2!) permutations when 2 vowels occur together, when we keep 2 vowels together, 3,4,5 vowels can also come together like for the permutation [IE]EEENDPNDC when we consider the cases when 3 vowels come together [10!/(3!2!) + 10!(3!/2!)/(3!*2!2!)] ways, it is already in the number of ways in which 2 vowels occur, so we add it once because 3 vowels among themselves can be arranged in (3!/3!)+(3!/2!)=4 ways and in case of 2 vowels it can be arranged in 2!(2!/2!)+2!=5 ways, hence we have add it once, when 4 vowels are considered, following the same process we will have to add up the number of possibilities 7 times and in case of all 5 vowels we will have to add it 2 times.. so the final form comes out to be
(12!/288)-[(11!/24)+(2!*11!/72)]+(10!*5)/24+7(9!*5/12)+2(8!*5/12) which is 739200 ways however in my textbook the answer given is 1646400 ways. I tried this question with the compliance method as well, in that since we have not to let any number of vowels occur together, I arranged them like this
VCVCVCVCVCVCVCV (V for vowel and C for consonants)
Now there are 8 places for 5 vowels and 7 places for 7 vowels, now since both V and C are repeating, we first arrange the consonants in 7!/(3!2!) ways and the 5 vowels in 8 places by 8P5 ways now as 4 E's are repeating, we have to divide 8P5 by 4!.. therefore the total number of ways of doing these 2 events simultaneously we will multiply both the ways so (7!/12)(8P5/4!) which yields out 117600. Kindly help or correct me wherever I am wrong..

Answer 1

The set of letters in the word is $~\{i,e,e,e,e,n,n,n,d,d,p,c\},~$ which is actually a multiset. You can run into problems when you try to use Inclusion-Exclusion against a multiset. I will illustrate the problems with simpler examples, in this answer.

First, see this article for an introduction to Inclusion-Exclusion. Then, see this answer for an explanation of and justification for the Inclusion-Exclusion formula.

Note that in the second link, the principle of Inclusion-Exclusion is justified by the idea that each element in $~S_1 \cap S_2 \cap \cdots \cap S_k~$ is counted once. This is the critical point.

---

$\underline{\text{Problem 1}}$

Given the set $~\{c,r,d,a,e,i\},~$ how many ways are there of selecting all 6 elements from the set (sampling without replacement) to form a sequence of letters, so that no two vowels are next to each other.

Following the easier approach in the comment of Nothing Special, immediately following the posted question, you know that there are $~3!~$ ways of permuting the three consonants.

For each such permutation, you have a tableau that resembles

____ consonant ____ consonant ____ consonant ____

So, the consonants form $~4~$ islands, each of which can contain only 1 vowel. There are 4 choices for which island to place the letter "a", then 3 choices for which island to place the letter "e", then 2 choices for which island to place the letter "i".

So, the computation has to be

$$3! \times (4 \times 3 \times 2) = 144.$$

Now, to get the same result with inclusion-exclusion, you let $~S~$ denote the set of all possible sequences, without any regard for whether the sequence has adjacent vowels.

Then, you let :

• $S_1~$ denote the subset of $~S~$ where the vowels $~a~$ and $~e~$ are together, in some order.

• $S_2~$ denote the subset of $~S~$ where the vowels $~a~$ and $~i~$ are together, in some order.

• $S_3~$ denote the subset of $~S~$ where the vowels $~e~$ and $~i~$ are together, in some order.

Then, you want

$$|S| - |S_1 \cup S_2 \cup S_3|. \tag1 $$

Let

• $T_0~$ denote $~|S|.~$

• $T_1~$ denote $~|S_1| + |S_2| + |S_3|.$

• $T_2~$ denote $~|S_1 \cap S_2| + |S_1 \cap S_3| + |S_2 \cap S_3|.$

• $T_3~$ denote $~|S_1 \cap S_2 \cap S_3|.$

Then, (1) above may be computed as

$$\sum_{r=0}^3 (-1)^r T_r.$$

Then:

• $\displaystyle T_0 = 6! = 720.$

• $\displaystyle T_1 = 3 \times 2 \times 5! = 720.$
  The factor of $~3~$ represents that you are computing $~3~$ terms which, by considerations of symmetry are identical. The factor of $~2~$ represents that in the computation of $~S_1,~$ the pairing "a,e" can appear as ---ae--- or ---ea---. The factor of $~5!~$ represents that with "a,e" paired, you are (in effect) permuting 5 elements, instead of 6.

• $\displaystyle T_2 = 3 \times 2 \times 4! = 144.$
  The factor of $~3~$ represents that you are computing $~3~$ terms, each of which represents the intersection of two of the $~S_k~$ subsets. Again, considerations of symmetry apply. The factor of $~2~$ represents that in the computation of $~S_1 \cap S_2,~$ the pairing "a,e" intersecting the pairing of "a,i" can appear as ---eai--- or ---iae---. The factor of $~4!~$ represents that with "a,e,i" now joined, you are (in effect) permuting 4 elements, instead of 6.

• $T_3 = 0.$
  To see this, note that when you intersect two of the subsets, you completely determine which vowel is in the middle. For example, $~S_1 \cap S_2~$ requires that "a" be in the middle. When you intersect this with $~S_3,~$ you are also requiring that (for example) "e" be in the middle, which is impossible. That is, a sequence of three vowels can only have one of the vowels in the middle.

So, you have that

$$\sum_{r=0}^3 (-1)^r T_r = 720 - 720 + 144 - 0 = 144,$$

which matches the result from the easier method.

---

$\underline{\text{Problem 2}}$

Given the set $~\{c,r,d,a,e,e\},~$ how many ways are there of selecting all 6 elements from the set (sampling without replacement) to form a sequence of letters, so that no two vowels are next to each other.

Problem 2, which is almost identical to Problem 1, actually involves a multiset, with the element "e" having multiplicity of $~2.~$ This consideration is going to wreak havoc with the attempt to employ Inclusion-Exclusion, as explained below.

Personally, after seeing the havoc, I looked unsuccessfully for a remedy. The key point is that it is vital that each element in $~S_1 \cup S_2 \cup S_3~$ be counted exactly once.

Again following the easier approach in the comment of Nothing Special, immediately following the posted question, you know that there are $~3!~$ ways of permuting the three consonants.

For each such permutation, you have a tableau that resembles

____ consonant ____ consonant ____ consonant ____

So, the consonants form $~4~$ islands, each of which can contain only 1 vowel. There are 4 choices for which island to place the letter "a", then 3 choices for which island to leave blank. Once these choices are made, the two remaining islands must each get one of the "e" letters.

So, the computation has to be

$$3! \times (4 \times 3) = 72.$$

Now comes the fun part.

One (ultimately unsuccessful) Inclusion-Exclusion approach is to label the two letters "e" as $~e_1~$ and $~e_2$.

Then, you let :

• $S_1~$ denote the subset of $~S~$ where the vowels $~a~$ and $~e_1$ are together, in some order.

• $S_2~$ denote the subset of $~S~$ where the vowels $~a~$ and $~e_2~$ are together, in some order.

• $S_3~$ denote the subset of $~S~$ where the vowels $~e_1$ and $~e_2~$ are together, in some order.

Then, you want

$$|S| - |S_1 \cup S_2 \cup S_3|. \tag1 $$

Let $~T_0, ~T_1, ~T_2, ~T_3,~$ be specified just as they were in Problem 1.

Then:

• $\displaystyle T_0 = \dfrac{6!}{2!} = 360.$
  The denominator represents that you have to adjust for the fact that in a constructed sequence, $~---e_1---e_2---~$ is not to be considered distinct from $~---e_2---e_1---.$

• The computation of $\displaystyle T_1~$ is now somewhat more complicated.
  $|S_1| = 2 \times 5! = 240,~$ since the "a" and the $~e_1~$ can appear in either order.
  By symmetrical considerations, $~|S_2| = 240.$
  Then, $~|S_3| = 120,~$ since a sequence like $~---e_1e_2---$ is not to be considered distinct from $~---e_2e_1---.$
  
  Therefore, $~T_1 = 600.~$

• The computation of $\displaystyle T_2~$ is also more complicated.
  To compute $|S_1 \cap S_2|~$ note that the letter "a" must be in the middle, and that the sequences $~e_1ae_2~$ and $~e_2ae_1~$ are not to be considered distinct. So, $~|S_1 \cap S_2| = 4!.$
  To compute $~|S_1 \cap S_3|~$ note that the letter $~e_1~$ must be in the middle, and $~ae_1e_2~$ is distinct from $~e_2e_1a.~$
  So $~|S_1 \cap S_3| = 2 \times 4! = 48.~$
  By reasons of symmetry, $~|S_2 \cap S_3| = |S_1 \cap S_3| = 48.$
  Therefore, $~T_2 = 24 + 48 + 48 = 120.$

• $T_3 = 0.$
  Here, the corresponding analysis from Problem 1 continues to be pertinent.

So,

$$\sum_{r=0}^3 (-1)^r T_r = 360 - 600 + 120 - 0 \neq 72.$$

So, something has gone haywire here. The only explanation is that with the multiset $~\{c,r,d,a,e,e\},~$ coupled with the consideration that in a constructed sequence, the "e"'s are indistinguishable, my attempt to compute $~|S_1 \cup S_2 \cup S_3|~$ failed to count each corresponding sequence exactly once.

---

A surgical remedy, that (perhaps) only applies to Problem-2 is to forgo the $~e_1,e_2~$ approach. Note that if you deduct $~240~$ from $~T_1,~$ and you deduct $~48~$ from $~T_2,~$ then you get the right answer.

An alternative approach is to reason that when faced with the multiset $~\{c,r,d,a,e,e\},~$ you should pretend that you have the set $~\{c,r,d,a,e,i\}.~$ Then, you would reason that the final computation should be halved, because each ---e---i--- sequence has a corresponding ---i---e--- sequence, and it is as if the "e" and "i" are indistinguishable.

The difficulty here is that some Combinatorics problems against multisets may be complicated enough to render the approach in the previous paragraph unworkable.

If you examine the 2nd Inclusion-Exclusion link, given at the start of this answer, you see that it proves the general validity of the approach (when applied against sets rather than multisets). If you are going to construct a generalized Inclusion-Exclusion approach to be applied against multisets, you are first going to have to prove that the approach is valid, no matter how unusual the problem is.

That is, if you are going to forgo constructing separate $~S_k~$ variables to be applied when you have elements with multiplicity greater than $~1,~$ you are going to have to identify and prove for which types of problems the approach will be valid.

So, whatever modification that you make to the Inclusion-Exclusion formula, so that it can be applied against multisets, on whatever type(s) of problems, you will have to prove that each element in $~S_1 \cup S_2 \cup \cdots \cup S_k~$ is counted exactly once.

I researched for about an hour on MathSE and I also tried googling. I didn't find anything that I could understand.