Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 4 down vote favorite
1

I read this problem in Cognition and Chance by Raymond Nickerson (the problem is stated not discussed)

A bag has 2n balls, two of which are marked '1', another two marked '2' and so 
on. m balls are chosen, find the probability that k pairs are still in the bag.

Here's my hand at the solution:

The $k$ pairs are chosen by $ n \choose k$. And let $x_i$ be the number of balls chosen of type $i$ (excluding the $k$ previously chosen) and these $x_i$'s should satisfy: $$ x_1 + x_2 + \cdots + x_{n-k} = m .\tag{1}$$ and clearly $$ 1 \leq x_i \leq 2 \tag{2}$$

Taking the generating function to solve this partition problem. $$ (x+x^2)^{n-k} \tag{3}$$ the $x^m$ term in $(3)$ is say $X_m$ and the answer becomes $n\choose k$$X_m$. However applying Binomial Theorem in $(3)$ gives a very simple answer. I am very skepticall about this answer. Generating functions hasn't been my friend lately. I am sure the approach is right though. Where have I gone wrong and what is the final expression for $X_m$

share|improve this question

2 Answers

up vote 1 down vote accepted

I assume the bag is to contain $k$ pairs, and no extra "singles" in it, as suggested by the approach of the posted question. And given that, in agreement with the post it follows that one wants to count the number of solutions to (1) with the restriction (2). Recalling from post: $$ x_1 + x_2 + \cdots + x_{n-k} = m ,\tag{1} $$ $$ 1 \leq x_i \leq 2. \tag{2}$$ Now note that restriction (2) imposes two inequalities on $m$. If the $x_k$ are all at their lower bound $1$ we get $n-k \le m$, while if they are all at their upper bound $2$ we get $m \le 2n-2k.$ So the restriction on $m$ in terms of $n,k$ in order that there be any ways at all to end up with $k$ pairs in the bag is $$ n-k \le m \le 2n-2k. \tag{3}$$

Now define $y_k=x_k-1$ so that $y_k \in \{ 0,1 \}$, and then we have $$y_1+\cdots +y_{n-k}=m-(n-k).$$ The number of solutions to this is the number of subsets of $\{1,...,n-k\}$ of size $m-(n-k)$.

Putting this count together with the $\binom{n}{k}$ ways to pick the pairs for the bag gives the result of the count (under restriction (3) above) as $$\displaystyle \binom{n-k}{m-(n-k)} \binom{n}{k}.$$ Note here that $0 \le m-(n-k) \le n-k$ follows from restriction (3). Of course this is only the number of ways, not the probability; divides by $\binom{2n}{m}$ for the probability.

EDIT: I realized that the above is right, but it is the count of how many ways there can be $k$ pairs in the bag, with perhaps also other single unpaired balls. In the notation of equation (1) of post (and above), whenever $x_k=1$ it means that the other ball labelled $k$ is in the bag of unchosen balls. Nothing changes in the calculations above, luckily --- I was just not thinking right about precisely what is being counted.

EDIT AGAIN: I now think that, if the two balls of a given number on them are considered distinct, which is necessary for the denominator to be $\binom{2n}{m}$, then there should be an extra factor of $2^r$ where $r$ is the number of variables $x_i$ in (1) which are to have the value $1$. This is because, if $x_i=1$, it means that one of the two balls labelled $i$ is to be in the bag, the other not. I also think that if the balls of the same number on them are considered indistinguishable a more complicated approach to the count may be needed, and also the resulting probability may be different than in the "distinguishable pairs" case above.

share|improve this answer
that was clear and precise! Thanks! – Vigneshwaren 2 days ago
Thanks, but I was not right in assuming the problem counts only cases of $k$ pairs in bag with no singles. Your set-up goes with that. See adjustment in answer after "EDIT". – coffeemath 2 days ago
(A) This is the probability of exactly $k$ pairs remaining in the bag at the end. From the wording of the question I'd have thought it's asking for ≥k pairs remaining in the bag at the end. (B) Even if solving the exactly-k-pairs problem as the OP does, I think doing this as solving equations is overkill. From each of the $n-k$ pairs we need to pick at least one to break up the pair, and then the remaining $m - (n - k)$ balls can be picked from any of the remaining $n - k$, so the second factor is $\binom{n - k}{m - (n - k)}$ directly. – ShreevatsaR 2 days ago
@ShreevatsaR -- I now think there should be an extra power of $2$ multiplying the count, if the two balls of a given number are distinct (which is needed if the denominator is to be $\binom{2n}{m}$). This is since in "breaking up the pairs" as you put it, one needs to decide which ball in a given pair ends up in the bag. With that inserted your approach in your comment makes equations unnecessary. – coffeemath 2 days ago
@coffeemath: Good point. If the balls of each pair are distinguishable, the probability is $\dfrac{\binom{n}{k}\binom{n-k}{m-(n-k)}2^{2(n-k)-m}}{\binom{2n}{m}}$. – ShreevatsaR 2 days ago
show 1 more comment
up vote 0 down vote

You have $n$ pairs, suppose pairs 1 to $k$ remain. Then you can take any $m$ balls out of the resting $2 n - m$, which you can select in $\displaystyle \binom{2 n - m}{m}$ ways. But the pairs remaining were selected arbitrarily, so it is really $\displaystyle \binom{n}{k} \binom{2 n - m}{m}$. The total number of ways of taking $m$ out of $2 n$ is $\displaystyle \binom{2 n}{m}$. Pulling everything together, the probability is: $$ \frac{\binom{n}{k} \binom{2 n - m}{m}}{\binom{2 n}{m}} $$ (no simplification apparent)

share|improve this answer
After you set aside $k$ pairs, $2n-2k$ balls remain, not $2n-m$. And you can’t take an arbitrary set of $m$ of these balls: you must take at least one ball from each of the remaining pairs. – Brian M. Scott Apr 30 at 20:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.