7
$\begingroup$

I am failing to wrap my head around a solution to a rather basic problem:

At a party, n men and m women put their drinks on a table and go out on the floor to dance. When they return, none of them recognizes his or her drink, so everyone takes a drink at random. What is the probability that each man selects his own drink?

The solution is: $$\frac{m!}{(n+m)!}$$

From what I intuit, $n!$ is the total permutations of the drinks among the men, and the above solution is the probability that all men get another man's drink, not necessarily that each one gets his own.

My solution was, there is a $\frac{1}{n+m}$ probability of the first man getting his drink, then $\frac{1}{n+m-1}$ for the second, $\frac{1}{n+m-2}$ for the third, ... , $\frac{1}{m+1}$ for the $n^{th}$. Resulting in a probability of $\prod\limits_{i=0}^{n-1} \frac{1}{n+m-i}$.

Can someone explain their thinking when approaching this problem?

EDIT

Issue arose from confusing variables and failing to identify that $$ \begin{align} \frac{m!}{(n+m)!} &= \frac{m!}{(n+m)(n+m-1)...(n+m-(n-1))(m!)}\\ &= \prod\limits_{i=0}^{n-1} \frac{1}{n+m-i}\\ \end{align} $$

$\endgroup$
8
  • 2
    $\begingroup$ The total number of permutations is $(n+m)!$. The number of permutations which leave the men unchanged is $m!$ $\endgroup$
    – lulu
    Jun 10, 2021 at 18:13
  • $\begingroup$ @lulu Sorry, I misread the solution. It is equal to $\prod_{i = 0}^{n - 1}\frac 1{n + m - i}$. $\endgroup$
    – WhatsUp
    Jun 10, 2021 at 18:17
  • 1
    $\begingroup$ There's one way to leave the men unchanged, and $m!$ ways to permute the women. $\endgroup$
    – saulspatz
    Jun 10, 2021 at 18:23
  • 2
    $\begingroup$ Is there something wrong with it ? $\frac {m!}{(n+m)!}=\frac 1{(m+1)(m+2)\cdots (m+n)}$ . Isn't that the same as your product? $\endgroup$
    – lulu
    Jun 10, 2021 at 18:39
  • 1
    $\begingroup$ @lulu The world is right side up again. Not familiar enough with factorials apparently -- I expanded it wrong on paper, leading to a mismatch. Thank you very much for your help. $\endgroup$
    – Rimov
    Jun 10, 2021 at 18:55

2 Answers 2

Reset to default
14
$\begingroup$

How many ways can you rearrange all the drinks? Answer: (m+n)!

Suppose all the men kept their drinks and only the women’s drinks got mixed up. How many possibilities are for this arrangement? Since there are m women, the answer is m!

So the odds of the men keeping their drinks is m! / (m+n)!

$\endgroup$
2
  • 2
    $\begingroup$ Elegant, clear, direct, and to the point. (+1). $\endgroup$
    – BruceET
    Jun 10, 2021 at 20:20
  • $\begingroup$ I think this is key insight -- remember to account for all groups pertaining to the problem, not just the one in question. Thank you. $\endgroup$
    – Rimov
    Jun 10, 2021 at 22:03
3
$\begingroup$

Notes: The most directly 'Relevant' of the links in the margin seems to be this, which also discusses a Poisson approximation. Also, an answer here discusses simulation of a similar problem, but explanations of the Perl program seem sparse. [Other links discuss probabilities for the (simpler) classical problem of derangements of items of a single type.]

Comment: Simulation approximates your suggested answer (+1), @Lulu's Comment, and @NicNic8's Answer (+1), for a specific case.

Suppose the population consists of $n = 3$ men (numbered 101, 102, 103). and $n = 4$ women (numbered from 1 through 4). Then the answer is $4!/7! = 0.00476.$

If we permute the population a million times and take the total score s of the population elements that are in their correct positions, then the total will exceed 300 precisely when all three men get their own drinks. The proportion of a million scores exceeding $300$ should approximate the desired probability to about three places.

set.seed(2021)
pop = c(1:4, 101:103)
pop
[1]   1   2   3   4 101 102 103

set.seed(2021)
s = replicate(10^6, sum(pop[sample(pop)==pop]))
mean(s > 300)
[1] 0.004821      # aprx 4!/7!
2 * sd(s > 300)/1000
[1] 0.0001385318  # aprx 95% margin of sim error

So the simulated value is $0.0048\pm 0.00014$ which includes $4!/7!.$

Notes: Demo of R code for one permutation:

set.seed(1234)         # for reproducibility
a = sample(pop); a     # permute sample
[1]   1   4 102   3 101   2 103
b = (a == pop); b      # in proper order?
[1]  TRUE FALSE FALSE FALSE  TRUE FALSE  TRUE
c = pop[a == pop];  c  # list who got own drinks
[1]   1 101 103        # two men got own drinks
sum(c)
[1] 205                # score
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .