0
$\begingroup$

Assuming any sequence of letters is a word, how many words can we form in such a way that the first two letters are different consonants while the last two letters are vowels?

$\endgroup$
  • 1
    $\begingroup$ Hello new user. The official recommendation is to describe what you have tried so far, and to pinpoint where you are stuck exactly. That way, people will be more sympathetic to helping you! $\endgroup$ – Roy O. Jul 24 '14 at 12:22
  • $\begingroup$ This is a programming problem - give me twenty minutes... $\endgroup$ – user117644 Jul 24 '14 at 12:23
  • 4
    $\begingroup$ My unofficial recommendation is to give the new user some time to edit this into a better question, instead of closing the question immediately. $\endgroup$ – Gerry Myerson Jul 24 '14 at 12:28
  • $\begingroup$ @mistermarko not on math stackexchange, it isn't. ;-) $\endgroup$ – Dustan Levenstein Jul 24 '14 at 13:00
2
$\begingroup$

A beginning:

There is no single formula for this. Therefore we have to organize the different types of cases, to which then known formulas apply.

There are $11$ slots where we have to write a letter. How many choices are there for the first two letters? They are of two different types, because of the double N. How many choices are there for the last two letters. Again there are different types.

Finally we have to fill in ("permute") the seven intermediate letters. There are no restrictions, but according to the types identified before the count will be different.

$\endgroup$
2
$\begingroup$

how many words can be formed using all letters in the word EXAMINATION

Assuming any sequence of letters is a word, how many words can we form in such a way that the first two letters are different consonants while the last two letters are vowels?

Assuming each letter is used only as many times as it occurs in the word.

First count the ways to place vowels and consonants, without considering identity or order within their type.

In addition to the two places on each ends, reserved for two consonants and two vowels respectively, there are seven places in the middle of the arrangement, which can hold three consonants and four vowels in $\frac{7!}{3!4!}$ ways.

$$\oplus\oplus\,\underbrace{\oplus\oplus\oplus\otimes\otimes\otimes\otimes}_{\frac{7!}{3!4!}\text{ permutations}}\,\otimes\otimes$$

Next count the ways to fill those places.

The consonants: XMTNN, can be arranged in $\frac{5!}{2!}-3!$ distinct permutations such that the pair of N do not simultaneously occupy the first two positions.

The vowels: EOAAII can be arranged in $\frac{6!}{2!2!}$ distinct permutations. If the vowels in the last two places have to be distinct this would be $\frac{6!}{2!2!}-2\times\frac{4!}{2!}$ permutations.

Thus there are $\frac{7!}{4!3!}\!\!\left(\frac{5!}{2!}-3!\right)\!\!\left(\frac{6!}{2!2!}\right)$ ways to arrange the letters as specified. ($340,200$)

There are $\frac{7!}{4!3!}\!\!\left(\frac{5!}{2!}-3!\right)\!\!\left(\frac{6!}{2!2!}-2\times\frac{4!}{2!}\right)$ ways if the vowels in the last two places have to be distinct. ($294,840$)

$\endgroup$
0
$\begingroup$
from itertools import *

vows = ('E', 'A', 'I', 'O')
cons = ('X', 'M', 'N', 'T', 'S')
count = 0

for m in permutations(list('EXAMINATIONS')):
    #print(m)
    if m[0] != m[1] and m[0] in cons and m[1] in cons and m[10] in
        vows and m[11] in vows:
        count += 1

print(count)

The answer is 33868800 if the program is correct. It is very much unoptimized.

$\endgroup$
  • $\begingroup$ The problem with this is you also permutate when the same letter is in the middle 7, causing repetition. $\endgroup$ – JoeyAndres Jul 24 '14 at 13:18
  • $\begingroup$ Do you think the answer is wrong or is the algorithm inefficient? $\endgroup$ – user117644 Jul 24 '14 at 13:39
  • $\begingroup$ You permutate even when the the same letters are in the middle. For example, E or I is not in the end, they are in the middle. There's two pairs of both letter. $\endgroup$ – JoeyAndres Jul 24 '14 at 13:52
  • $\begingroup$ I don't see any more optimization unless you convert this in C++ and and put -O3 in compiler. $\endgroup$ – JoeyAndres Jul 24 '14 at 14:32
  • $\begingroup$ NB Because there are two A's, I's and N's the same permutations are counted twice so it needs to be debugged. $\endgroup$ – user117644 Jul 24 '14 at 15:21
0
$\begingroup$

To solve this, we need to consider 3 cases:

  1. $N$ is in the first two letters.
  2. $E$ is in the last two letters.
  3. $I$ is in the last two letters.

To make it easier for my typing, let the propositions above be represented by the 3-tuple. e.g. $(T, T, T)$ means all propositions are true, $(F, F, F)$ means all propositions are false.

The following are the computations:

  1. $(F, F, F)$
    Since $N, E, I$ are all in the middle, we have 3 pairs of repetitions. To account for repetitions, the method used for counting is $$P([n_1,n_2,\dots,n_k], n) = \dfrac{n!}{n_1!n_2!\dots n_k!}$$ Where $n$ is the number of objects overall (including repetitions). And the $n_1, n_2, \dots, n_k$ are the repetition count. I will refer to this via $P([n_1,n_2,\dots,n_k], n)$ from now on.
    The number of words when all proposition are false are then, $$C_{first}*C_{last}*C_{middle}$$$${{4}\choose{4-2}}{{6}\choose{6-2}}P([2, 2, 2], 7) = 226, 800 $$Since I've laid out all the tools you need, from now on its just cold heart computation.

  2. $(F, F, T)$ $${{4}\choose{4-2}}{{6}\choose{6-2}}P([2, 2], 7) = 453, 600 $$

  3. $(F, T, F)$ $${{4}\choose{4-2}}{{6}\choose{6-2}}P([2, 2], 7) = 453, 600 $$

  4. $(F, T, T)$ $${{4}\choose{4-2}}{{6}\choose{6-2}}P([2], 7) =907,200$$

  5. $(T, F, F)$ $${{4}\choose{4-2}}{{6}\choose{6-2}}P([2, 2], 7) =453, 600$$

  6. $(T, F, T)$ $${{4}\choose{4-2}}{{6}\choose{6-2}}P([2], 7) =907,200$$

  7. $(T, T, F)$ $${{4}\choose{4-2}}{{6}\choose{6-2}}P([2], 7) =907,200$$

  8. $(T, T, T)$ $${{4}\choose{4-2}}{{6}\choose{6-2}}7!=1,814,400$$

Adding them all up, we get $6,124,800$, accounting for $3$ pairs of repetition.

$\endgroup$
  • $\begingroup$ How do you justify the three initial cases? You realize the OP gave the word EXAMINATIONS to begin with? $\endgroup$ – user117644 Jul 24 '14 at 14:24
  • $\begingroup$ @mistermarko If one of the $n$ is not in the start, then $n$ will be in the middle. If one or both of $a$ or $i$ are at the end, then $a$ and $i$ will be in the middle causing repetition. Can you elaborate further in that question? $\endgroup$ – JoeyAndres Jul 24 '14 at 14:30
  • $\begingroup$ Are you sure you're answering the question that was actually asked? $\endgroup$ – user117644 Jul 24 '14 at 14:34
  • $\begingroup$ @mistermarko Yes. If you read Christian Blatter's answer, we have exactly the same idea. Plus in Computer Science sense, this is actually good since it's almost like $O(\log(n))$ with a very low constant $k$, or even $O(1)$ for similar problems. $\endgroup$ – JoeyAndres Jul 24 '14 at 14:35
  • $\begingroup$ Here's the problem: the if clause is a direct translation of the OP's question but the result is totally different from yours. You should be able to give a different translation... $\endgroup$ – user117644 Jul 24 '14 at 14:44

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.