Tough counting problem

[Greeksquared]

Heres a counting problem that I figured out, but not in the most effecient way.

Each week you get 12 calls that will randomnly fall on any given day. What is the probability that you get atleast one call on each day.

At first I considered this problem the same as rolling a seven sided die 12 times but I couldnt come up with the right answer...not using basic probability. You can easily use this method of thought and run a simulation though.

So anyways I got this by finding all the combinations that have atleast one call on each day

6 1 1 1 1 1 1 (7!/6!)=7
5 1 1 1 1 1 2 (7!/5!)=42
4 1 1 1 1 1 3 (7!/5!)=42
4 1 1 1 1 2 2 (7!/4!/2!)=105
3 1 1 1 1 2 3 (7!/4!/2!)=105
3 1 1 1 2 2 2 (7!/3!/3!)=140
2 1 1 2 2 2 2 (7!/5!/2!)=21

12!/6!
12!/5!/2!
12!/4!/3!
12!/4!/2!/2!
12!/3!/3!/2!
12!/3!/2!/2!/2!
12!/2!/2!/2!/2!/2!

These are the only unique combinations, but each one of them can be rearranged so that the combination may be on each day. Thus there are 462 total possible outcomes in the sample space that meet the requirements. The second set of numbers is the actual number of different permutations that can be made in order out of the combination on the right. You multiply the two numbers together and you get the total number of distinct orders. The probability of getting that exact order would be (1/7)^12. Therefore there are 7^12 distinct orders. So you just add up all the distinct orders and divide by this and you get the answer .2285

Anyways..there is an easier way to get this but cant figure it out.

Counting is fun!

Thanks

[RocketManJames]

Ok, I'm not sure what I'm doing wrong here, because I get a totally different answer. Here's what I did, and I have a feeling I'm doing something really dumb here.

We have a total of 7 multi-choose 12 possibilities (or 18 choose 12), for 18564 combinations.

Now, if we force 7 days to have 1 call, we have 5 more calls to distribute amongst the 7 days. So we have 7 multi-choose 5 (or 11 choose 5) combinations. This gives us 462 combinations where each day has at least 1 call.

So, I get 462 / 18564, which is roughly 2.49%.

Where am I going wrong?

-RMJ

[aces961]

First of all you need to assume the calls are all identical.
Now the total ways to get 12 calls over 7 days is going to be 18 Choose 6 or (18!)/((12!*6!))=18564. To illustrate this let X be a call and let | be a break between days. You have
XXXXXXXXXXXX and 6 breaks must be inserted. One such insertation would be
XX|||XXXX|XXX||XXX. So you would have 2 calls sunday, 0 on monday or tuesday, 4 wed, 3 thurs, 0 fri, 3 saturday. If you notice the breaks are in the 3rd, 4th, 5th, 10, 14th, and 15th out of 18 spots. So to break up the calls you are in effect choosing 6 locations out of 18.

Now if we have 1 call at least per day. We only have 5 calls to break up over the 7 days. By the same logic with will be 11 choose 5 or 11!/(5!*6!)=462.

462/18564= approx .0249% for our answer.

As far as what the original poster did wrong, his calculations to get the number 462 as the correct number of ways to get 12 calls in the week with at least 1 each day is correct albiet long. The problem comes in finding the total ways to get the 12 calls over the 7 days. The method shown in the first reply and expanded upon in mine is correct assuming each of the calls are identical, which is what I would assume to be given the wording of the problem we are given. That is the question is equivilent to asking if you have 12 dollar bills how many ways can you distribute them to 7 people.

[Greeksquared]

I am afraid that the answer you came out with is not correct. As you might have guessed this is out of a probability text book and it gives .2285 as the answer in the back. If you want to check this just run a simulation.
Get a random number generator to produce 12 random numbers from 1 to 7 and repeat. You will see that the simulation gives a correct answer. This is also the answer that the book gives.

The way you worked it out is the same way that I worked it out at first. Each combination of the (18 c 12) is not equally likely to occur.

For example, lets say you have 4 calls and 2 days to spread them out on. There is only one way to put all the calls on the first day but there are 6 ways to put 2 calls on day one and 2 calls on day 2. Doing it your way would be (5 c 4) as the denominator and (3 c 2) as the numerator. This would give the result as .6 but the actual answer here would be 7/8. There are 16 different combinations and only 2 that give you all calls on either day. I think you have to lay out all the calls on a line and then assign them a day. You cant place walls to separate the calls. THe "last call" could very well be on day one and so on.

Remember..this is the exact same thing as rolling a seven sided die 12 times.

Anyways..thanks for the response

[RocketManJames]

Ok, after some discussion with a few people, here's where I went wrong. I correctly computed the NUMBER of valid configurations and the total number of configurations.

But, I *assumed* that all configurations are equally probable. And, this is clearly wrong.

I will now go back and see if I can find a clean solution to this problem.

-RMJ

[aces961]

Does the textbook you are getting this problem from cover generating functions. If so I'd read that section of the book and try applying it to this problem, I don't really have the time to go into it but this should be solvable using generating functions.

[Duke]

I have a simple and concise way to solve this, but alas it's a bit too large to fit in a comment.

Seriously, though, this is a tough problem. Not tough to solve, as your exhaustive method shows, but it's one of those problems that screams: "there is a simple way to solve me!" But oh how elusive that way is.

~D

[pzhon]

[ QUOTE ]
Each week you get 12 calls that will randomnly fall on any given day. What is the probability that you get atleast one call on each day.

[/ QUOTE ]

Let A1 be the event that no call comes on Sunday,
let A2 be the event that no call comes on Monday, etc.

The nice thing about these events is that it is easy to compute the probability of the intersection of any k of them: ((7-k)/7)^12 = p_k. That's just what you need to apply inclusion-exclusion.

You would like the probability of the complement of their union. The inclusion-exclusion principle (http://en.wikipedia.org/wiki/Inclusion-exclusion_principle) says that this is

1 - (P(A1)+...+P(A7)) + (P(A1/\A2)+P(A1/\A3)+...)-(P(A1/\A2/\A3)+...)+...-P(A1/\A2/\.../\A7)

= 1 - 7 p_1 + (7 choose 2) p_2 - (7 choose 3) p_3 + ... - (7 choose 7) p_7

= 9,218,880/40,353,607

= 0.228452


Mathematica code:
<ul type="square">
p[k_] := (7 - k)^12 /(7^12)
Sum[Binomial[7, k] (-1)^k p[k], {k, 0, 7}]
[/list]

[BruceZ]

I was just about to post my inclusion-exclusion solution when I saw pzhon had a similar idea. Here's mine anyway.

1 - [7*6^12 -
C(7,2)*5^12 +
C(7,3)*4^12 -
C(7,4)*3^12 +
C(7,5)*2^12 -
C(7,6)*1^12) ] / 7^12

= 0.22845244

[BruceZ]

[ QUOTE ]
First of all you need to assume the calls are all identical.
Now the total ways to get 12 calls over 7 days is going to be 18 Choose 6 or (18!)/((12!*6!))=18564. To illustrate this let X be a call and let | be a break between days. You have
XXXXXXXXXXXX and 6 breaks must be inserted. One such insertation would be
XX|||XXXX|XXX||XXX. So you would have 2 calls sunday, 0 on monday or tuesday, 4 wed, 3 thurs, 0 fri, 3 saturday. If you notice the breaks are in the 3rd, 4th, 5th, 10, 14th, and 15th out of 18 spots. So to break up the calls you are in effect choosing 6 locations out of 18.

Now if we have 1 call at least per day. We only have 5 calls to break up over the 7 days. By the same logic with will be 11 choose 5 or 11!/(5!*6!)=462.

462/18564= approx .0249% for our answer.

As far as what the original poster did wrong, his calculations to get the number 462 as the correct number of ways to get 12 calls in the week with at least 1 each day is correct albiet long. The problem comes in finding the total ways to get the 12 calls over the 7 days. The method shown in the first reply and expanded upon in mine is correct assuming each of the calls are identical, which is what I would assume to be given the wording of the problem we are given. That is the question is equivilent to asking if you have 12 dollar bills how many ways can you distribute them to 7 people.

[/ QUOTE ]

Note that you and RocketMan have solved the problem for the case where the calls obey Bose-Einstein statistics instead of Maxwell-Boltzmann statistics. That is, instead of taking each of the 7^12 arrangements to be equally probable, you have assumed that each of the indistinguishable arrangements of calls are equally probable.