Event with repitition

getback0 · 2010-10-10 18:00:32

Hello,

I am sure this is a piece of cake for you guys - but for some reason - i am not able to get it right (lets not focus on the reason for now! ).

The Problem:

Four people pick a number at random, each, between 1 and 10. In how many ways can at least 2 people pick the same number?

Deliberation:

n(S) = n(Sample space) = 10 * 10 * 10 * 10 = 10,000

E = at least 2 people pick the same number

~E = no two people pick the same number
n(~E) = 10 * 9 * 8 * 7 = 5,040

n(E) = n(S) - n(~E)
= 10,000 - 5,040
n(E) = 4,960 ..... (A)

Now that's one solution, and I get that.

My dilemma:

However, shouldnt the more direct method of defining possible outcomes for E yield this same answer? I tried but could not get it to match.

Here's what I did (clearly erroneous) and I am seeking your help to point out my error. Any help would be truly appreciated!

E = E1 U E2 U E3 U E4
where
E1 = two people pick the same number and the other two pick different numbers altogether
E2 = two people pick the same number and the other two pick the same number but different from the first one
E3 = three people pick the same number
E4 = all 4 pick the same number

AND

all these events are mutually exclusive.

Using the notation,

P(n, r) for permutations of n objects taken r at a time, and
C(n, r) for combinations of n objects taken r at a time

I feel,

n(E1) = ( P(10, 1)*C(4, 2) ) * ( P(9, 2)*C(2, 2) ) = 4,320

n(E2) = ( P(10, 1)*C(4, 2) ) * ( P(9, 1)*C(2, 2) ) = 540

n(E3) = ( P(10, 1)*C(4, 3)) * ( P(9, 1)*C(1, 1) ) = 360

n(E4) = ( P(10, 1)*C(4, 4)) = 10

However, with this, n(E) = 4,320 + 540 + 360 + 10
n(E) = 5,230 ..... (B)

Clearly, (A) and (B) do not agree.

What am I doing wrong? I dont want to grow any older thinking about this, but cant help it!!!!

Again, thanks for the guidance!

Leon

bobbym · 2010-10-10 20:13:30

Hi getback0;

Welcome to the forum!

Sounds like you are describing 2 pairs and just 2 pairs with N(E2). By actual count N(E2) = 270.

You can compute it like this:

Here is how I think about it.

Supposing we start with the first pair = (1,1) the second pair could be from 2 - 10 and each one is 4 choose 2.

Now we put a (2,2) in the first one, we can have from 3 - 10 in the second, each one 4 choose 2.

We continue like that:

Now everything works.

4320 + 270 + 360 + 10 = 4960

getback0 · 2010-10-14 18:03:34

Hello Bobbym,

I meant to get back sooner - first up, thanks for the detailed explanation! It makes sense to me - I was just struggling conceptually in that for E2, I felt I could -

1. Determine number of ways to split 4 people in groups of 2 IN ANY ORDER
2. Determine number of ways to pick 2 numbers from 1 - 10 and assign them in a specific order to all the combinations in #1

Since #1 above had no sense of an order, I used C(4,2)*C(2,2).

Also, since #2 above sounded like it had order involved, I used P(10,2).

... giving me C(4,2)*C(2,2)*P(10,2) = 540.

However, i now realize that using C(4,2) [number of combinations of 4 objects taken 2 at a time] would cause repititions in the splits I make. For example,

P-1 P-2 P-3 P-4
P-1 P-3 P-2 P-4
P-1 P-4 P-2 P-3
================ (=3) this right here is all possible partitions of 4 people in groups of 2. However, C(4,2) continues ...
P-2 P-3 P-1 P-4
P-2 P-4 P-1 P-3
P-3 P-4 P-1 P-2
================ (=6) all these partitions in the second group here are dups of the one above

I realize now that #1 above was really the unique number of partitions I could make (each partition is a group of combinations). So, in this case (1/2)*C(4,2) would the number of outcomes of #1 and hence -

(1/2)*C(4,2)*P(10,2) = 270

Now that sounds like a desperate attempt to match the right answer - however, I would feel better if you could weigh in on the following hypothesis -

The total number of unique partitions (k) of n objects when it is divided in p groups of m objects each for a given partition is -

k = (1/p)*C(n,m)

As always, thanks a lot for the guidance!

Leon

getback0 · 2010-10-15 05:07:50

OH NO - CORRECTION!!

The total number of unique partitions (k) of n objects when it is divided in p groups of m objects each for a given partition is -

k = C(n,m) / C( C(n,m) , p )

Does that seem right?

Leon

getback0 · 2010-10-15 05:17:31

may be not - I dont know any more

bobbym · 2010-10-15 05:49:38

Hi getback0 - Leon

may be not - I dont know any more

I have not been able to verify that formula. What I have been able to do is confuse myself.

getback0 · 2010-10-15 07:08:46

You sound a lot like me!!! Never mind - I think you set me on the right path - I will get back

bobbym · 2010-10-15 07:10:12

Hi Leon;

Tell me what you get!

getback0 · 2010-10-17 10:26:56

Alright! Alright! Alright!

I think I got it!!! until someone proves this wrong ...

The number of unique partitions (k) of n objects into p groups of m objects each (where n = m*p) is -

Hence, for the example, number of uniqe partitions of a group of 4 people into 2 groups of 2 each is -

C(4,2) * C(2,2) / P(2,2) = 6*1/2 = 3

This is verified in the example on the original post.

Here is why I think "k" should have the value from (1.1) -

1. The relation in (1.1) without the P(p,p) or p! is the familiar result for the outcome of an experiment that deals with picking m objects of n successively for p times when n = m*p

2. However, in this result, the same combination of objects appear multiple times - once for each of the p groups. In our example, [ (1,2), (3,4) ] is a partition.

This is different from [ (3,4), (1,2) ] if you define Groups - A and B - so, the C(4,2) * C(2,2) is trying to count both partitions. But if you consider them to be the same partition, just arranged in a different order, then this is just a rearrangement of the 2 partitions - in the general case, the p partitions would be rearranged p! times - inflating the results by a factor p!

3. Consequently, the final result needs to be (1/p!) times the outcome from C(n, m) * C(n - p, m) * C(n - 2p, m) * ... * C(m, m)

I tried verifying this with dividing 6 objects into groups of 2 objects -

conventionally this should have been C(6, 2) * C(4, 2) * C(2, 2) = 15 * 6 * 1 = 90

However, if you were to actually list the combinations down, you will see we start repeating combinations around in a different orde - rightly so, if you are looking for number of ways to group them in Groups A, B and C. However, if you are simply looking to split them in groups of 2, you will need to weed out 3! - 1 redundant counts - for each combination. If you do that, you should end with 15 unique partitions - which is the answer from 1.1

Thoughts bobby?

Leon

bobbym · 2010-10-17 12:59:21

Hi Leon;

I like what you are doing and the way you are thinking about the problem.
If that is what works for you then do that. Personally I find combinatoric reasoning like that to be difficult for me.

More important if I may say more important than your analysis is the fact that you enumerate and look!
I also like the way you empirically gained some confidence in your analysis by trying a few.

Just one more thing about the original question.

E2 = two people pick the same number and the other two pick the same number but different from the first one

This reminded me of a poker hand called 2 pair.
When you have 77 55 you have the same hand as 55 77.
The order of the pairs does not matter. That is what suggested 270 to me.

getback0 · 2010-10-17 13:53:49

Thanks for the encouragment, bobby! Much appreciated!

I agree - splitting a compound/complex problem down to simpler events which involve counting through combinations/permutations presents a very efficient way of solving problems. And the elaborate explanation you put together for n(E2) helped me get through my exercises quickly - so thanks again!

Caution: If only you are not tired of me talking about my thought process on this 1 problem, I would suggest reading on ... by the way, I am almost through with thinking about this one problem, so if I post again, very likely, it will be a different problem

I just wanted to find out what was leading me to get double the correct answer when I did [ C(4, 2)*C(2, 2) ] * P( 10,2 ) to arrive at n(E2) - because in my mind, the combinations-product was not accounting for any particular arrangement of numbers, while the permutations were - so I could not have been double counting.

But then in going through your explanation, I realized, that although I was using a combinations-product - the total partition of 4 people itself was being counted twice (for example, P-1 > [ (1,2), (3,4) ] and P-2 > [ (3, 4), (1, 2) ] - and the permutation (10,2) on top of this was not going to help.

Besides, I started thinking - why do combinations seem like they care for a particular order? And after some deliberation, it occured that combinations worked exactly the same as they are defined to - it was what I was looking to do with them - come up with unique-group of combinations and not combinations themselves (e.g. for my approach of using P(10,2), I could have counted either P-1 OR P-2 as they are the same partitions and I would have got the 270 answer - but they are different if you want to use C(10,2) for a final answer).

I guess a know a little more if I run into this situation again.

Leon

bobbym · 2010-10-17 15:25:25

Hi Leon;

Thanks for your explanation. It makes it little simpler to understand

I guess a know a little more if I run into this situation again.

Yes you do. The secret is practice, practice, practice.
Do as many as you can, get them wrong, get them right it does not matter just do them.
If you see a problem that starts with how many, that is for you.
Unfortunately you will get even better but you will never stop making errors in them.

Why? Around these parts there is a guy who is the best.
Works at a large secret installation and frequently is called in when math guys and physicists mess up.
Can solve mostly any problem, he says, "bobbym, Yer know why them fellas do all that there topology and logic?" "No, I do not, I says." "It's because they's a scared of combinatorics and probability."

He is obviously deranged but he is making one valid point, combinatorics and probability can trip anybody up.

I have to go practice now. See you later!

Math Is Fun Forum

#1 2010-10-10 18:00:32

Event with repitition

#2 2010-10-10 20:13:30

Re: Event with repitition

#3 2010-10-14 18:03:34

Re: Event with repitition

#4 2010-10-15 05:07:50

Re: Event with repitition

#5 2010-10-15 05:17:31

Re: Event with repitition

#6 2010-10-15 05:49:38

Re: Event with repitition

#7 2010-10-15 07:08:46

Re: Event with repitition

#8 2010-10-15 07:10:12

Re: Event with repitition

#9 2010-10-17 10:26:56

Re: Event with repitition

#10 2010-10-17 12:59:21

Re: Event with repitition

#11 2010-10-17 13:53:49

Re: Event with repitition

#12 2010-10-17 15:25:25

Re: Event with repitition

Board footer