PDA

View Full Version : Probability of Word within Word

abbott54
04-16-2008, 12:22 PM
Hello!

I'm in dire need of help as I've been working on this for a couple days now. I've been to the help center around school and have had three separate Prof. and student tutors give my a completely wrong answer (I checked with the Prof.). We received a problem with two pages of hints and explanations for how to approach but I still can't wrap my head around it. Here's the problem...

Each letter of the word MATHEMATICS is placed on a card and put in a hat. What is the probability that the you pull the word MATH out by choosing 4 cards without replacement?

The question doesn't clarify if order is necessary so I'd like to know both possibilities (that AHMT, MHTA and other variants still spell MATH, and I'd also like to figure out what the probability of drawing an M on the first, A on the second, T on the third, and an H).

I initially approached this problem by trying to figure out how many ways there are to spell MATH. M as first, and so on. M=2, A=2, T=2 so 2^3 ways or 8 ways to draw. This would be the numerator.

To solve for the other way for possibilities of spelling MATH I figure 4x3x2x1 (for the four letters in any order) which equals 24, one of which is exactly MATH.

The denominator is where I'm having a bit of trouble. I thought it would be a permutation of 11x10x9x8 but realized both M's, A's, and T's are treated the same in spelling. So given that there are 2 of three letters, I did a permutation of 8x7x6x5 plus the number of ways double letters could be used which ended up being (MM)AAx4, (TT)MMx4, (AA)TTx4, plus double letters without double letters (if that makes sense) ((MMx7x6)x4), ((AAx7x6)x4), ((TTx7x6)x4). I multiplied by four to indicate that the position of the double letter could be varied (MM**, *MM*, **MM, M**M). So all together the numbers add up to be 1680 for the permutation of MATHEICS, 12 for the double double combinations, and 504 for the double single combinations to equal 2196.

So my initial answer is 8/2196 or a probability of .003642.

For the other way it would be 24/2196 for a probability of .010929.

Can anyone help me out? :confused:

pka
04-16-2008, 01:06 PM
The answer if order is unimportant is \frac{{\left( {4!} \right)\left( {7!} \right)}}{{\frac{{11!}}{{2^3 }}}} = 0.0\overline {24}.
There are two ways to see this.
Think of the eleven cards as ordinary playing cards.
How many can you deal a hand of four that contain {A,H,M,T}?
A can be chosen \frac {2}{11}; H in \frac {1}{10}; M can be chosen \frac {2}{9}; and T can be chosen \frac {2}{8}.
But those four can be arranged in (4!).

So \left( {\frac{2}{{11}} \cdot \frac{1}{{10}} \cdot \frac{2}{9} \cdot \frac{2}{8}} \right)(4!) = 0.0\overline {24}.

Here is another way.
How many ways the rearrange MATHEMATICS: \frac{{11!}}{{2^3 }}.

How many of those begin with any arrangement of {A,H,M,T}: \left( {4!} \right)(7!)

If order matters then the answer is \frac{{7!}}{{\frac{{11!}}{{2^3 }}}} = \frac{{8\left( {7!} \right)}}{{11!}} = 0.0\overline {01}

abbott54
04-17-2008, 12:18 AM
I thought 11! works only if all of the elements are different. How do you take into account that IHM(1)E is the same as IHM(2)E? By that I mean the 1st M and the 2nd M. Both use different M's but they are the same possible spelling so instead of being 2 ways there is actually 1. If I can remember, the professor emphasized the fact that the answer was a little more difficult than that and was centered around the fact that 3 of the 11 letters are doubled.

pka
04-17-2008, 07:23 AM
The total number of ways to rearrange the word string ‘MISSISSIPPI’ is \frac{{11!}}{{\left( {2!} \right)\left( {4!} \right)\left( {4!} \right)}}.
The fraction’s denominator accounts for the fact that the 2 P’s are identical, as well as the 4 I’s and 4 S’s. That idea generalizes into a principle for handling repeating letters.
So ‘MATHEMATICS’ can be rearranged in \frac{{11!}}{{\left( {2!} \right)\left( {2!} \right)\left( {2!} \right)}} = \frac{{11!}}{8} ways.

abbott54
04-18-2008, 01:29 AM
Ok. I think I'm beginning to understand.

When you say MATHEMATICS can be arranged into 11!/2!2!2! or 11!/8, you mean that is the number of total possible four letter words without repeating? That is to say that by dividing 2!x2!x2!x1 is "removing" potential duplicates caused by the repeating letters? I'm sorry to keep asking questions. I'm just trying to fully understand the concept behind this problem. It could be the difference between a letter grade for me. What has thrown me for a loop is that in the hints, there's a suggestion of dividing possible four letter words into subsets which is why I did it in three sets (all letter combinations non repeating, double letters with double letters, and double letters with single letters). What did I not account for when I did that? Everything below is what was handed out...

Original Problem
The letters of the word MATHEMATICS are written on cards and dropped into a hat. 4 cards are drawn without replacement. What is the probability the 4 cards spell MATH?

HInts given with the problem are...

2. It is known that
P r[4 cards spell MATH] = n(ways to spell MATH)/n(all arrangements of 4 cards)
3. The number in the numerator of this fraction is easy to calculate.
4. The number in the denominator is not easy to calculate. Every ”easy”
solution that can be initially guessed relies upon an assumption that is unwar-
ranted. For example, one might guess that the number in the denominator is
equal to P (11, 4), but this guess can only work if each letter that occurs in the
word MATHEMATICS occurs only one time. The same problem arises in
the solution to problem 35 on the homework.
5. We should focus on calculating the number that should go in the denominator
of the fraction, since that is the really hard part of the problem. Here is an
outline of how that can be done.
Pr(4 cards spell MATH)= n(ways to spell MATH)/n(all arrangements of 4 cards)
i. We have to come up with a partition of the set that we are considering. In this
example, we want to compute the cardinal number of the set of 4 letter words
that can be made using the letters in the word MATHEMATICS. Point 4
suggests that difficulties are going to arise because this word has 3 letter types
which occur more than once. In fact, the letters A, M, and T occur exactly
twice. Each other letter type (and there are five of them) occurs exactly once.
So, we can partition this set into two subsets. One subset will be the set of
all four letter words which contain at least one M, A, or T. The other subset
will be the complement of the first subset. Explicitly, it is the subset of four
letter words which contain no A, M , or T. So the second subset contains only
four letter words composed of letter types that occur only once in the word
MATHEMATICS. It is easy to count the size of this second subset.
ii. However, it is still not easy to count the size of the first subset. We’ll need
to partition this subset even further. Since this subset contains at least one M,
A, or T, we may break it into the following disjoint subsets (what follows is a
description of the subsets)
1.Four letter words containing A but not T or M
2.Four letter words containing T but not A or M
3.Four letter words containing M but not A or T
4.Four letter words containing A and M but not T
5.Four letter words containing A and T but not M
6.Four letter words containing T and M but not A
7.Four letter words containing A, T, and M
You can check that these sets are all disjoint. For example, the word MAHE is
contained in the set desribed in 4. It cannot be in any of the other sets. There
is a similarity with this problem to problems in which Venn diagrams are used.
Here is a description of how to calculate the size of the set described in 3:
We want to calculate the number of four letter words that contain the letter M,
but not the letter A nor the letter T. There are two M’s to choose from, so a
four letter word can contain either one or two M’s. Because of this, it makes
sense to calculate the number of four letter words which contain exactly one M
and then calculate the number of four letter words which contain exactly two
M’s (but no A and T, of course) We will then add these two numbers together
to calculate the number of four letter words containing an M but not the letter
A nor the letter T. The number of elements in the sets described in 1 and 2 are
similarly calculated.
Here is a description of how to calculate the size of the set described in 4:
The four letter word now needs to contain an A and an M, but no T. There are
various ways this can occur. Here is a list of those ways:
A. The four letter word contains exactly one A and exactly one M
B. The four letter word contains exactly two A’s and exactly one M
C. The four letter word contains exactly one A and exactly two M’s
D. The four letter word contains exactly two A’s and exactly two M’s
Once the we calculate the number of words in each of these four cases, the
numbers can be added. This will give us the number of four letter words that
contain an A and an M, but no T. The calculation of the size of the sets described
in 5 and 6 is done similarly.
Here is a desciption of how the size of the set described in 7 may be calculated:
The word must have four letters, and there are three letter types that must be
chosen in 7. There are various ways this can occur. Here is a list of the possible
ways:
A. The four letter word contains exactly 2 A’s, exactly one M, and exactly one T
B. The four letter word contains exactly one A, exactly two M’s, and exactly one T
C. The four letter word contains exactly one A, exactly one M, and exactly two T’s
D. The four letter word contains exactly one A, exactly one M, and exactly one T
In the sets described in A., B., and C. all four letters in the word are used up.
This is not the case for the set decribed in D. The number of words in each of
these sets should be calculated than added.

Once again, I'm sorry for continuing. I greatly appreciate your help and patience.