1
$\begingroup$

In how many ways can the letters of word INTERMEDIATE be arranged such that relative order of vowels and consonants does not alter ?

$\endgroup$
  • $\begingroup$ (7C6)*2 is the answer? yes or no? $\endgroup$ – The Dead Legend Apr 11 '17 at 6:39
  • $\begingroup$ @UddeshyaSingh sorry pal don't know answer $\endgroup$ – Taylor Ted Apr 11 '17 at 6:43
  • $\begingroup$ I need a definition of 'relative order of vowels and consonants' to get my mind around this problem. Relative to each other? Relative to themselves? Relative to both themselves and to each other? I'm confuzzled. Give me examples of arrangements with a word like 'week' or 'nano'. Should it just be VCCVCCVCVVCV? $\endgroup$ – Arby Apr 11 '17 at 7:07
  • 1
    $\begingroup$ @Arby you rearrange the word however you want, but the vowels must remain in the same order, as do the consonnants $\endgroup$ – Alex Robinson Apr 11 '17 at 7:19
  • 1
    $\begingroup$ @Arby no it meansif number is 12345abc, then it can be arranged as 12ab345c and so on $\endgroup$ – Taylor Ted Apr 11 '17 at 7:59
5
$\begingroup$

Look at a simple problem, like ab12. The possible arrangements are ab12, 1ab2, 12ab, a1b2, a12b, 1a2b, so there are $\binom 4 2=6$ ways to place the letters. Think of it like lines and dashes like this:

ab12=--||

1ab2=|--|

12ab=||--

a1b2=-|-|

a12b=-||-

1a2b=|-|-

Extending this, we get ------|||||| which has $\binom {12} 6=924$ arrangments, i.e choose 6 places for the dashes in 12 positions, the lines filing the remaining positions.

$\endgroup$
  • $\begingroup$ Using the term "stars and bars" usually suggests a combination with repetition, which this is not. $\endgroup$ – N. F. Taussig Apr 11 '17 at 9:02
  • $\begingroup$ Should I change it to lines and dashes to avoid confusion? Went ahead and did it. $\endgroup$ – Arby Apr 11 '17 at 9:13
  • 2
    $\begingroup$ You realized the key point of the problem, which is that choosing the position of the consonants completely determines the arrangement since there is only one way to order the consonants in their chosen positions and only one way to order the vowels in the remaining positions. $\endgroup$ – N. F. Taussig Apr 11 '17 at 9:22
  • $\begingroup$ Yeah, it felt right when I worked it with smaller numbers, up to 4 consonants and 3 vowels. I could see the way forward at that point. Thanks to all for the clarifications needed to get to the heart of things, the wording of the problem I found confusing. $\endgroup$ – Arby Apr 11 '17 at 9:24
  • 1
    $\begingroup$ @Arby now it is making some sense. Thanks $\endgroup$ – Taylor Ted Apr 11 '17 at 9:24
4
$\begingroup$

Yet another way to look at this problem is to realize it's a "permutation with repetition" in disguise. If there were no repetitions, and no restrictions on the order, there would be $12!$ ways to arrange the letters. However, in your problem, of these $12!$ ways you do not want to count the $6!$ permutations of the vowels, nor do you want to count the $6!$ permutations of the consonants. So, you must divide them out, meaning the answer you are looking for is:

$$ \frac{12!}{6!6!}=924 $$

$\endgroup$
  • $\begingroup$ Do you mean permutation of a multiset rather than permutation with repetition? $\endgroup$ – N. F. Taussig Apr 11 '17 at 9:29
  • $\begingroup$ @N.F.Taussig Yes, this is what I was referring to. I have always heard of it called permutation with repetition. $\endgroup$ – wgrenard Apr 11 '17 at 9:56
1
$\begingroup$

Okay, I know this can be dead wrong. But anyway, Here's my attempt. Hope it helps
We are suppose to conserve the order of "IEEIAE" and "NTRMDT". Point to be noted is that both are 6 letter long. Now think of this. $$X,V_1,X,V_2,X,V_3,X,V_4,X,V_5,X,V_6,X$$ Be the order for arrangement with 'X' as blank spaces.Their is only one way to arrange the vowels so let's ignore it. (To conserve the order.) Now we have 7 potential places for consonants . So we Do $^7C_6 *1$.( multiplied by one because we will NOT BE PERMUTATING IT).
If we repeat the procedure by taking Vowels in blanks instead of consonants, we get another $^7C_6$.

Thus according to me, answer should be $^7C_6 * 2$.
Improvements are always welcome. Cheers.

$\endgroup$
  • 1
    $\begingroup$ Your answer is incorrect. There can be more than one consonant in your blank spaces. For instance, the sequence NTRIEMDTEIAE preserves the relative order of the vowels and consonants. $\endgroup$ – N. F. Taussig Apr 11 '17 at 9:00
1
$\begingroup$
  • If there are no vowels (or no consonants), there is one interleaving.
  • If there are both vowels and consonants, we can start with either.
  • If we start with a vowel (consonant), what follows is an interleaving of one less vowel (consonant) and the same number of consonants (vowels).

So the number of ways $S$ to interleave $v$ vowels and $c$ consonants is given by the recurrence

$$S_{v \; c} = \begin{cases} 1 & \text{if $v = 0$ or $c = 0$}\\ S_{v-1 \; c} + S_{v \; c-1} & \text{otherwise} \end{cases} $$

Solving this directly gives

$$ S_ {6 \; 6} = 924$$


Solving the recurrence requires $(v-1)(c-1)$ additions: far more operations than the $2 \,min(v-1 , c-1)$ multiplications that the combination method requires.


Thank you for improving the layout of the above, dear reader. I'm no expert at Mathjax.

- Nor at maths :(. I got the initial conditions wrong. Corrected.

$\endgroup$
  • $\begingroup$ If you have five vowels and one consonant, you have six possible arrangements: BAEIOU, ABEIOU, AEBIOU, AEIBOU, AEIOBU, AEIOUB. $\endgroup$ – N. F. Taussig Apr 11 '17 at 9:06
  • $\begingroup$ @N.F.Taussig Ouch! Thanks - corrected. $\endgroup$ – Thumbnail Apr 11 '17 at 9:21
  • $\begingroup$ I used the cases environment (see systems of equations in this tutorial) to improve the formatting. Your answer reminds me that I need to review (revise) my knowledge of recurrence relations. $\endgroup$ – N. F. Taussig Apr 11 '17 at 9:38

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.