Distinct permutations of x items from n items

Question: Find the distinct number of permutations of four letters of the word MATHEMATICS.

The answer is 11P4/(2!)^3 = 990

Is this correct? This question along with the answer is from a module from my course, so this is all the details that I am able to provide.

My understanding of this question is how many distinct 4 letter words can be formed from the word 'MATHEMATICS'. Therefore, a word like 'MAME' is valid. I know that using 11P4 alone will not suffice because it will say that there are 4 ways to create the 4 letter word MAME from the word 'MATHEMATICS'. So, we I will need to adjust the output of 11P4, and this is where I am stuck. The answer divides 11P4 by (2!)^3. I think this represents the 3 non-distinct letters in the word 'MATHEMATICS' (i.e. M,A,T) which have two copies each. Using Sage, the answer I have is 2,454 which is not the same as the answer provided. Here is the code I wrote:

#Input according to question
inputQ='M A T H E M A T I C S'.split(' ')

#Same input, but each letter in input is distinct
inputTest='M1 A1 T1 H E M2 A2 T2 I C S'.split(' ')

print inputQ
print inputTest

#Number of letters to form from the given input
choice=4

ansQ=Permutations(inputQ,choice).list()
ansTest=Permutations(inputTest,choice).list()

print 'Total distinct permutations of ' + str(choice) + ' letter word(s) from the word ' + ''.join(inputQ) +':' ,len(ansQ)
print 'If each letter in '+ ''.join(inputQ) + ' were distinct: ', len(ansTest)


What if I only want 1 letter? Then the answer would be 8, which I got by manually listing down all possibilities. But what it the general formula for this sort of problem?

-
Please precise your question. Do you want 4-letter words composed by letters from the word "MATHEMATICS" ? If yes, can we choose the same letter several times? For example, is "MAME" a possible word? – Djaian Nov 2 '10 at 12:03
Also if I am not very wrong this question is exactly similar to math.stackexchange.com/questions/2372/… – Quixotic Nov 2 '10 at 14:17
Notice that the question (that I thought was the original question): How much 11-letter words can we find by permuting only 4 letters in the word "MATHEMATICS" is an interesting one. I cannot find the answer in a trivial manner. – Djaian Nov 2 '10 at 14:56
Yes,your question seems interesting. – Quixotic Nov 2 '10 at 15:04
@Djalan: Indeed it is an interesting question. Just to confirm, that question is asking how many unique words can be found by rearranging any 4 letters? So, 'TICSMATHEMA' would be valid, correct? – Sara Nov 4 '10 at 15:32

In order to solve this question, you should separate into different cases.

First, let's try to find all the 4-letter words that have different letters.

Like Debanjan pointed out, this leads to 8*7*6*5 = 1680 words. The idea for this is just to consider you have 8 possibilities for the first letter, but for the second letter you only have 7 possibilities since it must be different from the first one, and so on.

Now, let's count the word that have 2 "M", but all other letters are different. You have 7 choices for another letter, and 6 for the last letter. However, the 2 "M" might be anywhere in the word, thus you multiply this by the number of permutation, which is given by $\frac{4!}{2!2!} = 6$ Thus, there are 7*6*6 = 252 such words.

[ EDIT: Here I need to explain something, as Ross commented out.

I only count 252 such words and not 504, because in the 42 choices of letters, I can choose "S" and "C", but I can also choose "C" and then "S". So either you have to divide the 7*6 by 2, or you only allow permutations that don't change the order of the first other letter chosen and the second other letter chosen.

Sorry, I didn't want to explain this in details, but it is true it is needed, in order to avoid confusion. ]

There are also 252 words with 2 "A" and all other letters different.

There are also 252 words with 2 "T".

Finally, there are 6 words with 2 "A" and 2 "M", 6 words with 2 "A" and 2 "T" and 6 words with 2 "M" and 2 "T".

Total: 1680 + 252 + 252 + 252 + 6 + 6 + 6

-
Not quite. The number of permutations of MMXY is 4!/2!=12. So the 252s should be 504s – Ross Millikan Nov 2 '10 at 13:49
And what about 2M and 2C's, you see this making this problem more hard since number of distinct letters is 8 which is sufficiently large.And By hard I mean under exam constraints ofcourse. – Quixotic Nov 2 '10 at 14:13
@Debanjan: Sorry but I don't understand your comment. There is only 1 C in "MATHEMATICS". So you cannot have 2 C's in your word. – Djaian Nov 2 '10 at 14:32
Sorry I meant 2M and 2A on the same 'MMAA' and cases like this MMA* ? Did you consider all such cases if yes then I didn't understood your approach :( – Quixotic Nov 2 '10 at 14:45
@Debanjan: I am quite sure my approach is correct. First, count all 4 letter words that have different letters, then count all 4 letter words that have 2 M and 2 other letters, but the 2 other letters must be different (possibly 1 A, but not 2 A's). Finally, count all words with 2 pairs of letters. – Djaian Nov 2 '10 at 14:46

Note: This answer presumes that the question is "How many four-letter words can be formed using the letters of the word 'MATHEMATICS'." So MAME should be counted as a word.

The provided answer, ${}_{11}P_4 / (2!)^3$, is not correct.

Let's temporarily change the question to "How many distinct rearrangements are the of the letters of MATHEMATICS?", that is, how many 11-letter words can we form. If the letters were all distinct, the answer would be 11!, that is, ${}_{11}P_11$. But the letters are not all different, so we must adjust. We can do so as in the original problem: First, attach subscripts to identical letters, so that the letters are in fact all distinct, making 11! "words".

Now we need to erase subscripts. First take the Ms. There are two of them, M1 and M2, and swapping these does not change a "word" when we're ignoring subscripts. So there are 11!/2 words if we ignore the subscripts on M. Proceeding similarly, we find that there are $11!/(2*2*2)$ distinct words when all the subscripts are erased.

We need factorials when we have more than two of a letter. Suppose there were three Xs. Then there are 3! ways of rearranging the Xs, and all these ways lead to the same word when subscripts are erased. So the adjustment would be to divide by 3!. (Really this is happening with the Ms too, since 2! = 2.)

In general: Suppose we have a total of $n$ letters, including $c_1$ copies of one letter, $c_2$ copies of the second letter, . . . , and $c_i$ copies of the $i^{\rm th}$ letter. Then the total number of words we can make is

$$n! \over { c_1!c_2!\ldots c_i! }$$

Notice that this formula works even for letters that aren't replicated, since 1! = 1.

So far so good. The trouble is that the original problem does not ask for words formed from all the letters, just from four at a time. And here the trick doesn't work. We do need to adjust, but we can't simply divide by 2! when there are two copies of a letter, because some of the words don't contain all the copies of that letter! The adjusting trick, as described, works only when all copies of the letter are necessarily in the word, i.e., when each word contains all letters.

To see this even more clearly, suppose I had asked for words of two letters formed from the letters of MATHEMATICS. Would the answer be ${}_{11}P_2/(2!)^3$? Certainly not, since this expression is not even an integer.

Is there a way of phrasing the question so that the provided answer is correct? I don't see it, and I find it doubtful anyway, for the same reason as in the preceding paragraph.

-

After the edit by OP,here is a similar problem and solution.

-
No, I don't think so, I have a strong feeling that my translation is correct.However it will be nice if OP confirm it. – Quixotic Nov 2 '10 at 11:54
Yes the question is not clear.Better lets wait and see what (s)he have to say on this :) – Quixotic Nov 2 '10 at 12:05

I came across this on this website today purely by chance. I struggled with this particular problem for a long time before arriving at an answer that turned out to be wrong. After some more work I eventually found the following solution. I hope it is correct.

There are a total of 11 letters, 3 of which are duplicated: AA, MM, TT, HEICS

There are 4 mutually exclusive ways of permutation that add to the solution:

1. Permutation of all different letters: $\frac{8!}{4!}$=1680

2. Permutation of 2 from 5 letters (excluding all 3 duplicates), HEICS, and then each of this permutated with each pair of duplicates. There are $\frac{5!}{2!}$ = 20 permutations of HEICS and then permutations of these with each of the duplicate, e.g. HEMM, gives $\frac{4!}{2!}$ = 12, giving a total of 12 x 20 = 240 and with 3 pairs we get 240 x 3 = 720

3. The 3 duplicate pairs with each other, e.g. AAMM, $\frac{4!}{2!2!}$ = 6 for each pair, giving 6 x 3 = 18

4. One pair of duplicates permutated with one each of the other 2 pairs, e.g. MMAT, $\frac{4!}{2!}$ = 12 and with 3 pairs there are 12 x 3 = 36 permutations.

So altogether, there are:

1680 + 720 + 18 + 36 = 2452 permutations of 4 letters from MATHEMATICA.

-
are you having difficulties editting your own answer? If you log-in, the software should allow you to do so. – Willie Wong Mar 3 '11 at 12:06