2
$\begingroup$

I am struggling with questions of this format, where you are trying to find the number of possible subwords where you have duplicate letters in the original word.

I have tried both counting the number of 5 letter subwords where each identical letter is treated as being distinct then removing duplicates, and counting how many unique full length words can be formed then subtracting cases identical in the last 4 characters. I'm not sure which approach is easier, but in both cases I can't work out a way of quantifying the factor I need to divide by/subtract respectively.

Edit: Note, this is considering each letter in MANHATTAN like a scrabble tile, so you only have 3 As, 2 Ts, etc.

$\endgroup$
2
  • $\begingroup$ Is the answer 5! = 120 ? Considering if repetition isn't allowed, then only M,A,N,H,T can be used $\endgroup$ – Safdar Faisal Apr 13 at 4:10
  • $\begingroup$ If there is no repetition, then there are exactly 5 letters: M, A, N, H, and T. Is this the right way to interpret your problem? Or, do you mean that there can be any subwords, but we don't want to double count with the same letters? $\endgroup$ – Pavan C. Apr 13 at 4:16
4
$\begingroup$

Immediately following, is my (incorrect) interpretation of the OP's intent. See (for example), the comment following this answer. I have added a 2nd response to the end of my answer.


In this problem, you are lucky that there are only 5 distinct letters, M, A, N, H, T, and that repetitions are not allowed.

Therefore, it doesn't matter, (for example) which of the 3 A's are used to complete
the set $S = \{$M, A, N, H, T$\}.$

That is, you are being asked how many subwords can be formed, rather than (for example) how many ways there are of selecting 5 specific letters from the original group.

The problem is completely answered by asking how many ways there are in permuting the letters in the set $S$.




Edit
Per OP's intent, to treat the letters like scrabble tiles.

There are $3$ A's, $2$N's, and $2$T's.
For me, the simplest approach is to take off my shoes.

I will break this up into cases, letting $T_k$ represent the enumeration of Case $k$.

$\underline{\text{Case 1}:~3~\text{A's are used}}$
Either an additional double letter is used, or it isn't.
If it is used, it can be either N,N or T,T.
There are $\binom{5}{2} = 10$ ways of forming a word using AAANN.
Therefore, $T_{1a} = 2 \times 10 = 20.$

If no double letter is used, then there are
$\binom{4}{2} = 6$ ways of selecting the two off letters, from M,N,H,T, to use and then $(5 \times 4) = 20$ ways of positioning the off letters.

Therefore, $T_{1b} = 6 \times 20 = 120.$
Therefore, $T_1 = T_{1a} + T_{1b} = 20 + 120 = 140.$


$\underline{\text{Case 2}:~2~\text{double letter pairs are used}}$
There are $\binom{3}{2} = 3$ ways of selecting two pairs from AA,NN,TT.
Suppose that AA,NN are selected.
Then, you have (3) choices for the off letter.
Suppose that you are forming a word using AA,NN,M.
There are $\binom{5}{1} \times \binom{4}{2} = 30$ ways of positioning the letters.

Therefore, $T_2 = 3 \times 3 \times 30 = 270.$


$\underline{\text{Case 3}:~1~\text{double letter pair is used}}$

There are $\binom{3}{1} = 3$ ways of selecting the pair to use from AA,NN,TT.

Assume that $AA$ is selected. Then, there are $\binom{4}{3} = 4$ ways of selecting the 3 off letters from among M,N,H,T.

Assume that a word will be formed by AA,M,N,H.
There are $(5 \times 4 \times 3) = 60$ ways of positioning these letters.

Therefore, $T_3 = (3 \times 4 \times 60) = 720$.


$\underline{\text{Case 4}:~2~\text{No double letter pair is used}}$
There are $5!$ ways of permuting M,A,N,H,T.

$T_4 = 120.$


Therefore, the total enumeration is

$$T_1 + T_2 + T_3 + T_4 = 140 + 270 + 720 + 120 = 1250.$$

$\endgroup$
2
  • $\begingroup$ I think my question was unclear with saying repetition not allowed, I will update it and make it clearer. What I mean is you cannot repeat a letter more than it appears in the word, like they were scrabble tiles. $\endgroup$ – ajax2112 Apr 13 at 4:50
  • $\begingroup$ @ajax2112 Thanks for the warning. I will edit my answer accordingly. $\endgroup$ – user2661923 Apr 13 at 4:57
3
$\begingroup$

The answer should be

$\displaystyle 2 \cdot \frac{5!}{3!2!} + {4 \choose 2} \frac{5!}{3!} +3 \cdot 3 \cdot \frac{5!}{2!2!} + 3 \cdot 4 \cdot \frac{5!}{2!} + 5! = 1250$

We have $3A, 2N, 2T, 1H, 1M$ and there are five terms in the above working.

First term - $3 A's$ and we choose a double, $N$ or $T$.

Second term - $3 A's$ and we choose two distinct letters from remaining four.

Third term - we choose two doubles from $A, N$ and $T$ and then last letter from remaining three.

Fourth term - we choose one double and three distinct letters from remaining four.

Fifth term - all $5$ letters are distinct.

$\endgroup$

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.