Looking at the ‘combinations with repetitions’ explanation on this site (near bottom of page, dealing with 3 scoops of ice cream from five possible flavors):
I was trying to figure out the best way of quickly calculating the various sub-combinations possible, i.e “all unique flavors”, “two the same” and “all three the same”. Obviously the probabilities of these sub-groups sums to one.
My real-life problem is the elevator at work (9 floors), so if 5 people get in, what are the probabilities that “everyone leaves on a different floor”, “only 2 share the same floor”… all the way up to “everyone gets out on the same floor”.
Problem 1 is straightforward.
First scoop has 5 possibilities. Second 5 also. Third also 5.
555=125.
Second problem is more tricky. It is a variant of the birthday problem. I am going to assume that the reqired floors are uniform random and independent for each person. Without this assumption you need more info.
This problem is not wuite small enough for you to write out all the possibilities and sort them as you wish. However, doing this is always insightful and reveals the calculatio method. I recommend sumplifying to five floors and three people and see what you get.
Five floors three people.
Total number of possibilities is 555=125.
Number of possibilities where each person chooses a unique floor is 543=60
First person has five unique floors to choose. Second can choose between remaining four and the third has three.
Number of possibilities where two people choose the same floor is as follows:
There are 3 possibilities for choosing two people to opt for the same floor. 3C2=3.
5 possibilities for the doubled floor and 4 remaining choices for the other persin. 54=20.
So, 320=60.
The remaining option is where all three choose the same floor.
First person in has 5 possible choices. Second has only one: he must choose the same as the first. Ditto the third.
This gives 511=5 possibilities.
125 in total which was what you expected.
Now apply the same kind of careful reasonong with 5&9 and see what you get.
Do you care to distinguish between “2 people get out on the same floor, the other 3 all get out on different floors” (one pair) and “2 people get out on one floor, another 2 get out on another floor, and the last person gets out on yet another floor” (two pair)?
(And, similarly, do you care to distinguish between “3 people get out on one floor, and the other 2 each on different floors” (three-of-a-kind) and “3 people get out on one floor, and the other 2 share another floor” (a full house)?)
[Of course, actual elevator usage statistics are almost certainly not in keeping with the 5 people making independent, uniformly random floor selections…]
The “special technique” ( C(n+r-1, r) ) really is elegant! I don’t remember if it has a special name.
By examples, here’s one way to count the “sub-combinations” you’ve defined:
With three cones of five flavors:
three –> C(5,1) = 5
two & one –> C(5,1) * C(4,1) = 5*4 = 20
one & one & one –> C(5,3) = 10
With five cones of nine flavors:
five –> 9
four & one -> C(9,1) * C(8,1) = 72
three & two -> 9 * 8 = 72
three & one & one -> 9 * C(8,2) = 252
two & two & one -> C(9,2) * 7 = 252
two & one & one & one -> 9 * C(8,3) = 504
one & one & one & one & one -> C(9,5) = 126
These sum to C(13,5) = 1287 as expected.
For example, in the “three & one & one” case, there are nine ways to pick the triplet and C(8,2) ways to pick the two singletons from the eight leftovers. The “two & two & one” case has the same count distributions, so the same answer, but I’ve shown the calculation differently since “all roads lead to Rome.”
But please note that (assuming flavor choices are independent) these counts don’t lead to probabilities. That’s because each “quintuplet” case can arise in only one ordering, while the “five singletons” case can arise from 5! orderings, “three & one & one” case from 5!/3! orderings, and so on.
The real-life probabilities are going to depend strongly on the circumstances. For example, it’s almost never the case in a 9-story building that floor usage is equal and that when 5 people enter the elevator they are independent.
IOW, probabilities often differ from possibilities.
The one key issue is whether everyone is unique, or whether we are just talking about “a person” and you don’t care who.
The case “Sally gets off on the 4th, Fred on the 5th” is different from “Fred gets off on the 4th, Sally takes the 5th”. However, “one person gets off on the 4th and one gets off on the 5th” describes both these cases, if identities are irrelevant.
Cool, I remember seeing the formula long back for number of zero and non-zero solutions of equation: x1 + x2 + x3 ..+xr = n and deriving it the same way in my head And feeling good about myself:-).
Another question on combinations:
Lets say we have 8 boxes and 8 balls, each ball kept in its designated box. They are taken out and then put back again randomly one in each box. What are the chances that no ball goes back to the box where it was initially kept?
Such an arrangement is called a derangement. As the ball count becomes large, the chance an arrangement will be deranged rapidly approaches the reciprocal of Euler’s number, i.e. 0.3679.
This is the only right answer to the real world problem. You can do the textbook calculations assuming independence and uniformity, but you should never fool yourself into thinking that it matches up with what’s actually going on.
With the elevator problem, you wouldn’t have nine possibilities. No one is going to get out on the floor they entered from. Presumably your riders are all entering at the same time*, so there are eight floors they may be going to.
It would be more complicated if some people may have come from other floors.
ZenBeam: Good spot - I should have clarified that everyone’s getting on at the Ground floor, and there’s floors 1-9 above it.
More generally, I made the assumptions that everyone is truly independent (i.e. that Fred and Sally aren’t team mates and therefore always going to leave together on the 7th floor) to simplify Xema’s point, and that I don’t know anyone (so am not bothered by md2000’s case where I have to identify who gets off at each floor).
Indistinguishable:
Yes, this was part of my problem, that such sub-combinations obviously become more numerous as you increase from simple case such as 3C2.
I’ll need to work through the examples by j_sum1 and septimus to get them clear in my mind (thanks!) , but at first glance they’re both going to help.
This all came about when I got into the lift with five other people and we all chose different floors and thought, “What are the odds of that?”.
If people are actually picking floors independently and uniformly, the vector describing how many people get off at each floor follows a multinomial distribution with n equal to the number of people on the elevator and p_i equal to 1/9 for all i.
Thats correct!
I hadn’t studied derangement earlier so I solved it in following way. [spoiler]
suppose we have n balls (and n boxes) . suppose W(n) equals the number of ways such that no ball goes into its correct box.
the number of ways such that atleast 1 ball goes into its correct box = n! - W(n)
= number of ways where exactly 1 ball goes to correct box +
number of ways where exactly 2 balls goes to correct box +
number of ways where exactly 3 balls goes to correct box +
:
:
number of ways where exactly n balls goes to correct box
So,
n! - W(n) = nC1W(n-1) + nC2W(n-2) + nC3W(n-3)…nCnW(0)
W(0)=1 , W(1) = 0 , W(2) =1, W(3)=2
calculate W(4),W(5),W(6) ,W(7), W(8) using the above formula. => W(4)=9, W(5)=44, W(6)=265, W(7)=1854 , W(8)=14833
answer to this puzzle is = (8!-W(8)) / 8! ~ 0.63[/spoiler]
of course for larger values of balls and boxes, I am screwed with this method.
yes correct, a computer program would be helpful in solving for larger values of n.
Thanks for sharing the link. Looks like other problems there will also be interesting to study. There is one interesting problem I share which calls for a computer program to solve, people can try:
Two perfect logicians, S and P, are told that integers x and y have been chosen such that 1 < x < y and x+y < 100. S is given the value x+y and P is given the value xy. They then have the following conversation.
P: I cannot determine the two numbers.
S: I knew that.
P: Now I can determine them.
S: So can I.
Given that the above statements are true, what are the two numbers?
