1
$\begingroup$

I want to calculate the number of $8$ letter words that can be formed using the letters of the word $TIDE$. However, in any word only one permutation of the word $TIDE$ should be present. That means among the $8$ letters I should not have four twins.

For example, $ITDETTDD$ is a valid word since I have only one permutation of $TIDE$ and I cannot get other if i remove already obtained Permutation. But the word $TTIIEEDD$ or $TDEIDEIT$ is not valid since I can get two possible permutations.

My try: we have $8$ positions. Each position can have $4$ choices from $T$, $I$, $D$ and $E$.

So total words =$4^8$.

From this if we remove all the words of the form $TTIIEEDD$ we get all the words that contain only one string of $TIDE$.

Now all the words of the form $TTIIEEDD$ is $\frac{8!}{2!2!2!2!}$

So required answer is $$4^8-\frac{8!}{2!2!2!2!}=63016$$

EDIT: Well i got a different way to do it:

Since each letter must appear atleast once,In four places if we fix the letters $T$, $I$, $D$, $E$. then remaining four places have the following possible cases

Case $1.$ Words of the form $TIDETTTT$ which means eaxctly one letter repeated four times in other four places. So number of such words is

$$\binom{4}{1} \times \frac{8!}{5!}$$

Case $2.$ words of the form $TIDETTTD$ where exactly two letters occupy in other four places, but one repeats thrice.So all such words are

$$\binom{4}{2} \times 2 \times \frac{8!}{4!2!}$$

Case $3.$ Words of form $TIDETTDD$ where exactly two letters occupy in other four places,but each repeated twice. Number of such words are

$$\binom{4}{2} \times \frac{8!}{3!3!}$$

Case $4.$ Words of form $TIDETTDE$ where exactly three letters occupy other four places and among them one repeats twice. Number of such words are

$$\binom{4}{3} \times 3 \times \frac{8!}{3!2!2!}$$

Hence final answer will be sum of all the above which is

$$8! \left(\frac{4}{120}+\frac{1}{4}+\frac{1}{6}+\frac{1}{2}\right)=38304$$

$\endgroup$
4
  • $\begingroup$ I do not understand the problem. Is the "For example" part of the problem description, or is it your interpretation? I do not see TIDE at all in ITDETTDD. $\endgroup$ Jan 9 '16 at 18:29
  • $\begingroup$ No the word $TIDE$ need not be present in that order. if am able to form $TIDE$ if they are in random order also we count it. $\endgroup$ Jan 9 '16 at 18:31
  • 1
    $\begingroup$ I think he means the string contains each of the 4 letters appears at least once but at not all letters appear twice; i.e. at least 1 letter only appears once. His mistake, and mine, was thinking not all letters had to appear. IIIIIIII is not acceptable because TDE don't appear. $\endgroup$
    – fleablood
    Jan 9 '16 at 18:43
  • $\begingroup$ A better way to ask the question would be how many strings of eight letters can be formed using the letters T, I, D, E in which each letter appears at least once but not all of the letters appear twice? $\endgroup$ Jan 9 '16 at 19:50
2
$\begingroup$

The wording of the problem is unfortunate, since the usual meaning of string is sequence of consecutive letters.

You have dealt with the "TIDE does not occur twice" correctly. However, you have not counted the words in which TIDE occurs at least once correctly, for there certainly are not $4^8$ such words.

To count them, we can either divide into cases or use Inclusion/Exclusion. We carry out most of the Inclusion/Exclusion process. There are $4^8$ words. Let us count the bad words, in which at least one of the letters is missing. There are $3^8$ words in which T is missing, and the same with the other letters. If we add up, getting $4\cdot 3^8$, we are double-counting the bad words in which, for example, T and I are both missing. There are $2^8$ such words, and there $\binom{4}{2}$ ways to choose the two missing letters.

So our next estimate of the number of bad words is $4\cdot 3^8-\binom{4}{2}2^8$. However, we have subtracted too much, for we have subtracted one too many times the words in which for example all of T, I, D are missing.

Now put things together.

$\endgroup$
1
$\begingroup$

This is tedious but.

Case 1: There is one T,I,D,E and 4 Es. Or in other words one T,I,D and 5 Es. There are 8*7*6 ways to place the T,I,D so there are 8*7*6 = 8!/5! total ways to do this.

Case 1b: The E was arbitrary. 4*8!/5! ways to have 5 of a single letter.

Case 2: There is one T, I, D, E. 3 E's an extra D. Or in other words one T,I, 2 Ds and 4 E. There are 8*7 = 8!/6! ways to place the T, I. There are there ar ${6 \choose 2}$ ways to place the Ds. So 8!/6!*6!/4!2! = 8!/4!2! total..

Case 2b: the D and E were arbitrary so $(4*3)*8!/4!2!$ ways to do 4 of a letter and 2 of another.

Case 3: TIDE plus 2 Ds and 2 Es. Or 1 T,I and 3 D's and 3 Es. Again 8!/6! ways to do the T,I. And ${6 \choose 3} ways to do the D. So 8!/3!5! total.

Case 3a: Arbitrary: 4*3 chooses for which two letters are tripled and 4*3/2 as order of choosing the 2 doesn't matter. So (4*3/2)8!/3!5! total.

Case 4: TIDE plus and an extra IDE plus an extra E. Or in other words two of every letter but T and 3 Es. There's ${ 8 \choose 3}$ ways to place the Es. ${5 \choose 2}$ ways to place the Ds, and ${3 \choose 2} = 3$ ways to place the Is. So $8!/5!3! * 5!/3!2! * 3!/2! = 8!/3!2!2!$.

Case 4a: Arbitrary: 4 choose for the triple letter; 3 for the single letter.

$(4*3)8!/3!2!2!$ total.

So total is $ 8!/4!2! + (4*3)*8!/4!2! + (4*3/2)8!/3!5! + (4*3)8!/3!2!2!$

$= 8!(1/4!2! + 12(1/4!2! + 1/2*3!5! + 1/3!2!2!))$

$= 8*7*3*5 + 4*7*3*5 + 2*3*8*7 + 8!/2$

$= 28(60 + 15 + 12 + 6*5*4*3*2) = 28(87 + 720) = 22596$. I think.

$\endgroup$
1
$\begingroup$

There are 65536 total combinations of the available letters and there are 2520 combinations containing two of each letter. Therefore:

65536-2520 = 63016

EDIT#1:

If we must also exclude those combinations that lack a letter (24712) then:

65536-2520-24712 = 38304

There is no overlap in the two sets of exclusions so they can be directly subtracted.

EDIT#2:

To generate the exclusion counts, I used an Excel spreadsheet:

enter image description here

I placed all 65536 combinations in columns A through H. Column I represents the four twins exclusion:

In I1

=IF(AND(COUNTIF(A1:H1,"T")=2,COUNTIF(A1:H1,"I")=2,COUNTIF(A1:H1,"D")=2,COUNTIF(A1:H1,"E")=2),1,0)

and copy down. Column J represents the missing letter exclusion; so in J1:

=IF(OR(COUNTIF(A1:H1,"T")=0,COUNTIF(A1:H1,"I")=0,COUNTIF(A1:H1,"D")=0,COUNTIF(A1:H1,"E")=0),1,0)

and copy down..........the exclusion values are just the simple sums of columns I and J.

$\endgroup$
9
  • $\begingroup$ Except you must have at least 1 of each letter. $\endgroup$
    – fleablood
    Jan 10 '16 at 0:31
  • $\begingroup$ @fleablood ...........why........................ $\endgroup$ Jan 10 '16 at 0:38
  • $\begingroup$ "However, in the word only one string of the word TIDE should be present." and "So required answer is $4^8−8!/2!2!2!2!=63016$ But there is an error in my approach as my book answer is different. " It's badly stated but it's clear in the explanation that the OP seems to be assuming the letters TIDE are always used. Although you are right, it is not explicitly stated. And as such yours is the correct answer as stated but it isn't the intended answer. $\endgroup$
    – fleablood
    Jan 10 '16 at 0:46
  • $\begingroup$ @fleablood So all four letters must appear at least once, but there cannot be four twins. $\endgroup$ Jan 10 '16 at 0:51
  • $\begingroup$ That's my understanding. The post isn't clear but that's how I interpreted it. (After first interpreting it the way you did.) $\endgroup$
    – fleablood
    Jan 10 '16 at 0:53

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.