What do you think?

bobbym · 2011-05-02 20:40:50

Yes! I can not find the hole in my program. But it would be better if he agrees with your answer. That way we would have a method!

gAr · 2011-05-02 21:09:34

Debugging a code is tougher than analyzing the problem!

If you don't mind, can you post the code?

Last edited by gAr (2011-05-02 21:11:00)

bobbym · 2011-05-02 21:52:28

Hi gAr;

I do not mind but it is a functional language and hard to understand. I have working with it for 12 years and I still do not have it.

n=8;

pruned=Partition[#,2]&/@Permutations[{1,1,2,2,3,3,4,4},{n}];

pruned=Union[Partition[Sort[#]&/@ Flatten[pruned,1],n/2]];

ans=Select[pruned,Count[#,{1,1}]+Count[#,{2,2}]+Count[#,{3,3}]+Count[#,{4,4}]==0&];

gAr · 2011-05-02 22:02:44

Hi bobbym,

Yes, it's difficult for me to understand!

bobbym · 2011-05-02 22:13:31

Basically what it does is set up the balls as numbers {1,1,2,2,3,3,4,4} because they use less memory and are faster. Then it generates all permutations of {1,1,2,2,3,3,4,4}, there are 2520 of them. Next they are partitioned into boxes {1,1,2,2,3,3,4,4} -> {{1,1},{2,2},{3,3},{4,4}}

These boxes then have there 2 entries sorted {{1,2},{2,1},{3,3},{4,4}} ->{{1,2},{1,2},{3,3},{4,4}}

The union command eliminates redundant partitions.

The select command only counts the permutations that do not have {1,1},{2,2},{3,3},{4,4} in them. (Meaning no boxes have the same elements )

gAr · 2011-05-02 22:31:45

Good idea!
I'm searching for equivalent commands in sage.
But it's strange that our answers don't match!
Can you give the output you get for different colored balls in 4 boxes?

12,23,34,14
12,24,13,34
13,23,24,14

Any other than above?

bobbym · 2011-05-02 22:58:18

Hi gAr;

Can you give the output you get for different colored balls in 4 boxes?

Isn't that the answer we are looking for?

Here are my 90 ways to have 8 balls in 4 boxes with no box having the same color.

gAr · 2011-05-02 23:12:23

All right, Your answer is correct!

I missed
12,12,34,34
13,13,24,24
14,14,23,23

so permuting theem gives

Similarly, my other two answers for 5 colors and 6 colors would be wrong too!

bobbym · 2011-05-02 23:31:11

Okay, so that is the missing 18 that we were having a problem with.

This is the entire message I sent and received from him.

bobbym wrote:

I have 8 balls, 2 are red, 2 blue, 2 green, 2 white. I have 4 boxes
marked B1,B2,B3,B4. I want to distribute the eight balls into the 4
boxes, 2 balls in each.
What is the probability that no box has the same colored balls?
I worked the total number of ways to arrange the 8 balls in the 4
boxes is 2520. By direct count I have as an answer of 4 / 7. I have
tried the principle of inclusion and exclusion but I can not get 4 / 7
as the answer.

At the time I had the wrong answer too!

He wrote:

The total number of ways of dividing up the 8 balls into 4 groups of
2 (in distinguishable boxes) is 8!/[2!.2!.2!.2!] = 2520
From this we must subtract the number of ways with one or more boxes
having the same colour.
Suppose the two reds are in 1 box chosen in 4 ways. We have the
other 6 distributed in 6!/[2! 2! 2!] = 90 ways. So with red in 1 box
and the other 6 balls distributed without restriction the number of
ways is 4 x 90 = 360. However we could choose which colour in 4
ways and so the overall total with 1 colour is 4 x 360 = 1440
We make up a table so that we can apply inclusion-exclusion
1 colour in 1 box, no. of ways = C(4,1) x C(4,1) x 6!/[2!]^3 = 1440
2 colours in 2 boxes " " = C(4,2) x C(4,2) x 4!/[2!]^2 = 216
3 colours in 3 boxes " " = C(4,3) x C(4,3) x 2!/2! = 16
4 colours in 4 boxes " " = C(4,4) x C(4,4) x 1 = 1
Then using inclusion-exclusion the number of arrangements with at
least one box with 2 balls of the same colour is
1440 - 216 + 16 - 1 = 1239
Number of arrangements with no box with balls of the same colour
= 2520 - 1239 = 1281
1281
------- = 61/120
2520

bobbym wrote:

Thanks for your immediate reply. Sorry for the delay in responding
but I have been checking and rechecking so that we do not waste your
time.
A friend and I have been looking at the problem. We have come up with
a different answer than yours but we cannot find the hole in our idea
or yours. We are hoping you can.
I am coming up with 15 / 47 as the answer and my friend gAr is coming
up with the amazing formula:
(4*4!) / (4! + C(4,2) (4!/2!) + 4*4! + 3*4! ) = 3 / 11
The only thing we can think of that is causing your answer to be too
high is that we are both coming up with a lot less total ways then
2520. This is due to the fact that in a box (r,b) is the same as
(b,r). So I am getting 282 total ways to arrange the balls while he
is getting 264.
Despite the differences between mine and gAr's we are not even close
to yours. What are we doing wrong?

He wrote:

I cannot say what you are doing wrong without seeing your
calculations. But you are mistaken if you think that I am not
counting (r,b) in a box the same as (b,r). The expression
8!
-----------
2! 2! 2! 2!
has all the 2! factors in the denominator exactly to do this.

gAr · 2011-05-02 23:47:57

Ok.

I cannot say what you are doing wrong without seeing your
calculations. But you are mistaken if you think that I am not
counting (r,b) in a box the same as (b,r). The expression
8!
-----------
2! 2! 2! 2!
has all the 2! factors in the denominator exactly to do this.

This definitely overcounts.
E.g.
1,2,1,2,3,4,3,4 and 1,2,2,1,4,3,3,4 should be treated the same!

bobbym · 2011-05-02 23:53:43

Hi gAr;

I agree that in my opinion he has the wrong answer! I do not think I can convince him. But I do not want to embarass anyone or have a protracted battle over who is right and who is wrong. I am just going to say "Thank You" and let it go. He is a good mathematician and anyone can make an error.

Also thanks for working on it with me. I had a lot of fun, hope you did too.

gAr · 2011-05-03 00:11:10

Ok, maybe you can post my explanation and ask his opinion, and also tell him the reason why it overcounts?

Call the 4 colors a,b,c,d.
Case 1: All boxes have same colored balls - aa,bb,cc,dd - 4! ways

case 2: 2 boxes have same colored balls - aa,bb,cd,cd ; aa,bd,cc,bd etc. - C(4,2) * 4!/(2!) ways

case 3: 1 box has same colored balls - aa,bc,cd,bd etc. - 4 * 4! ways

case 4: All boxes have different colored balls -

ab,bc,cd,ad; ab,bd,ac,cd; ac,bd,bc,ad; - 3 * 4! ways

ab,ab,cd,cd; ac,ac,bd,bd; ad,ad,bc,bc - 3 * 4!/(2!*2!) ways

bobbym · 2011-05-03 00:16:21

Hi gAr;

Yes, that is my answer. It is interesting to know that at one of the strongest forums in the world there is a variant of this problem and they are getting it wrong too!

If you think you can change his mind I will submit it to him. Do you?

gAr · 2011-05-03 00:29:42

Hi bobbym,

Yeah, give it a last try. Open mind would think again.
But we can't help if he chooses to ignore, can we?

bobbym · 2011-05-03 00:39:39

I will try again. You see the problem is that he only knows the abstract side of math. Because he has never programmed them, he has never seen the 2520 permutations. I mean seen them with his eyes. If he had, he would know that their are many duplicates and he would come around to our way very quickly. It is the difference between Classical math and Experimental math!

gAr · 2011-05-03 00:57:08

Yes, very true! Like windows users refusing to learn any other OS.

Anyway, like I said before, try to explain him that comparing {1,2,1,2,3,4,3,4} and {1,2,2,1,4,3,3,4} is not same as
{{1,2},{1,2},{3,4},{3,4}} and {{1,2},{2,1},{4,3},{3,4}}

bobbym · 2011-05-03 01:03:09

Hi gAr;

That is going to be the toughest part to comprehend. I have sent our work to him.

gAr · 2011-05-03 01:11:44

Okay, anyway, we have our answer which we believe in.
Can you give the denominator you get for 5 and 6 colors, perhaps we can check the sequence from oeis?

bobbym · 2011-05-03 01:27:40

Hi;

3, 7, 282, 6210 ... but there is nothing over there for it. For 12 balls it is too large for my method to get.

gAr · 2011-05-03 01:36:20

Hi bobbym,

If we check the sequence without simplification, i.e 3,21,282,6210 ( I hope 6210 is not the simplified one), it shows A000681

bobbym · 2011-05-03 01:43:50

I thought I was going crazy. I was there yesterday and was even reading about the sequence in a book. Today, I kept putting in 7 instead of 21, that is why I could not get it back!!!! Stupid mistake!

There is a reference I think to one of the books, I think by Comtet or maybe Lint that has this sequence. They call it a permutation inversion. Anyway the book talks about balls in boxes but they can have 3 in each box. Anyway he does not explain it well enough, so I was unable to use it yesterday.

gAr · 2011-05-03 02:00:26

Okay!
But the next answer I get doesn't agree with the sequence, bad!!

bobbym · 2011-05-03 02:08:26

Hi gAr;

Maybe that is because they are not the same sequences. Just because it agrees with 4 terms does not mean that it has to continue.

I am going to take some time to do some chores, I will see you later.

gAr · 2011-05-03 02:15:10

Yeah, see you later!

bobbym · 2011-05-03 14:06:25

Hi gAr;

I received this as apparently his final answer.

bobbym wrote:

Just wanted to say how much I have enjoyed speaking with you on this
problem. gAr and I have done as you requested and hope we can explain
ourselves correctly.
Call the 4 colors a,b,c,d.
Case 1: All boxes have same colored balls - aa,bb,cc,dd = 4!
ways.
Case 2: 2 boxes have same colored balls - aa,bb,cd,cd ; aa,bd,cc,bd
etc. = C(4,2) * 4!/(2!) ways.
Case 3: 1 box has same colored balls - aa,bc,cd,bd etc. = 4 * 4! ways
Case 4: All boxes have different colored balls:
ab,bc,cd,ad; ab,bd,ac,cd; ac,bd,bc,ad; = 3 * 4! ways
ab,ab,cd,cd; ac,ac,bd,bd; ad,ad,bc,bc = 3 * 4!/(2!*2!) ways
P(no matching balls in any box) =
= (3 * 4!+3 * (4!/(2*2)) / (4! + C(4,2)(4! / 2) + 4*4! + 3*4! + 3* 4!/ (2*2))
= 90 / 282
Thanks for listening, respectfully yours;
bobbym

He wrote:

Looking at your working you have been counting the number of
DIFFERENT ways that the balls can be placed in the boxes. However
with probability calculations we cannot just work with the different
ways something can happen, we must deal with equiprobable events. For
example if you distribute 8 balls in 4 boxes at random the number of
DIFFERENT ways is as shown below
| *** | | ** | *** | occupancy 3, 0, 2, 3
The diagram begins and ends with a '|' symbol but otherwise all the
DIFFERENT ways are given by the number of ways we can arrange 3 '|'s
and 8 *'s. That is 11 objects with 3 alike of one kind and 8 alike
of a second kind.
11!
------ = C(11,3) = 165
3! 8!
However the different arrangements are not equiprobable. For example
getting all 8 balls in the first box can happen in only 1 way but
getting the arrangement I show above could occur in many ways since
the first ball could be in any of the 3 boxes and the second could
also be in any of the 3 boxes that are shown as occupied. In fact
the number of possible EQUIPROBABLE events is given by 4^8 = 65536
Compare that with 165 which gives the number of DIFFERENT
arrangements.
In my solution to the original problem of not having 2 balls of the
same colour in one box I have dealt with equiprobable events,
counting each ball as distinct, while your method has worked eith the
number of DIFFERENT events.

Math Is Fun Forum

#926 2011-05-02 20:40:50

Re: What do you think?

#927 2011-05-02 21:09:34

Re: What do you think?

#928 2011-05-02 21:52:28

Re: What do you think?

#929 2011-05-02 22:02:44

Re: What do you think?

#930 2011-05-02 22:13:31

Re: What do you think?

#931 2011-05-02 22:31:45

Re: What do you think?

#932 2011-05-02 22:58:18

Re: What do you think?

#933 2011-05-02 23:12:23

Re: What do you think?

#934 2011-05-02 23:31:11

Re: What do you think?

#935 2011-05-02 23:47:57

Re: What do you think?

#936 2011-05-02 23:53:43

Re: What do you think?

#937 2011-05-03 00:11:10

Re: What do you think?

#938 2011-05-03 00:16:21

Re: What do you think?

#939 2011-05-03 00:29:42

Re: What do you think?

#940 2011-05-03 00:39:39

Re: What do you think?

#941 2011-05-03 00:57:08

Re: What do you think?

#942 2011-05-03 01:03:09

Re: What do you think?

#943 2011-05-03 01:11:44

Re: What do you think?

#944 2011-05-03 01:27:40

Re: What do you think?

#945 2011-05-03 01:36:20

Re: What do you think?

#946 2011-05-03 01:43:50

Re: What do you think?

#947 2011-05-03 02:00:26

Re: What do you think?

#948 2011-05-03 02:08:26

Re: What do you think?

#949 2011-05-03 02:15:10

Re: What do you think?

#950 2011-05-03 14:06:25

Re: What do you think?

Board footer