Combinatorics and probability question

Question

Suppose we have $20$ balls numbered $1,2,...,20$. Each day we pick a single ball randomly.

1) What's the probability of picking all $20$ balls in $22$ days ?

2) What's the probability of picking only $1 \,and\, 2$ in $4$ days (Atleast 1 times each) ?

Attempts and Thoughts -

1) I thought that we could pick $20$ days out of the $22$ - $\binom{22}{20}$. Now there are $20!$ distinct orders for all the $20$ balls in the $20$ picked days. What's left is to put $2$ balls in the days left - $20^2$ options for that and over all - $\binom{22}{20}\cdot 20!\cdot 20^2$. I thought this might be true until i encountered another approach suggesting - $\binom{20}{1}\cdot \binom{22}{3}\cdot 19! + \binom{20}{2}\cdot \binom{22}{2}\cdot \binom{20}{2}\cdot 18!$. The leftmost part reffering to when a ball is being picked $3$ times and the right most to $2$ balls being picked twice.

Which approach is right? What have i done wrong?

2) First approach - there are exactly $2^4$ options considering $1,1,1,1$ or $2,2,2,2$. So we get - $2^4 - 2= 14$ options.

Another approach suggested $22^4 - 2\cdot 21^4 +20^4$ which comes out of basic inclusion-exclusion.

Would like to hear you thoughts about my problem. Thanks in advance.

Answer 1

For the (1), your approach is not quite correct. The problem is that the procedure you outlined will over-count some of the ways to choose the balls. For example consider the following two ways of following your instructions:

1. Option $1$:
   1. Pick the days numbered $1,2,\dots,19,20.$
   2. On these days, pick balls numbered $1,2,\dots,19,20$.
   3. On days $21$ and $22$, pick ball $20$.
2. Option $2$:
   1. Pick the days numbered $1,2,\dots,19,21.$
   2. On these days, pick balls numbered $1,2,\dots,19,20$.
   3. On days $20$ and $22$, pick ball $20$.

These both result in the same ball distribution, but are counted separately by your method. The other solution you wrote uses careful accounting to avoid this.

For (2), you are answering a different question than the other solution. You are counting the number of ways to pick four balls comprising one $1$s and $2$s, with both present. The other method is the number of ways to pick four balls where at least one is a $1$ and at least one is a $2$.

Answer 2

Problem 1

Your approach to the first question is incorrect : there is overcounting happening.

To see why this is the case, let us see the steps you are using :

• Fix a subset of $1,...,22$ : can be done in $\binom{22}{20}$ ways.

• Arrange for $20$ balls to be picked in these turns : done in $20!$ ways.

• Two turns are left, and they may be allotted freely , hence in $20^2$ ways.

The overcounting comes from the fact that it is possible to start from different subsets and still get the same order using the free choice of the third step.

---

Example :

Start with the subset $\{1,...,20\}$, and arrange for ball $1$ to be picked on the first day, ball $2$ on the second day , ball $3$ on the third day etc. by the second step. Now for $21$ and $22$, let balls $19$ be picked on day $21$ and ball $20$ on day $22$. Thus, the final order is $1,2,3,...,20,19,20$.

Now, start with the subset $\{1,...,18,21,22\}$. Arrange for ball $1$ to be picked on the first day, ball $2$ on the second day , ..., ball $18$ to be picked on the $18$th day, ball $19$ on the $21$st day and ball $20$ on the $22$nd day. Now, on the remaining days, let ball $19$ be picked on day $19$, and ball $20$ on day $20$. This gives the same order as the previous order, but with a different subset.

Therefore, a direct multiplication of the combinations resulting from the above steps is over counting.

---

The way the other solution takes care of this problem, is not to isolate which subset of $20$ elements contains $20$ different balls, but rather which ball appears twice/thrice (no ball appears more than thrice : this would leave $19$ different numbered balls to be distributed in $18$ days, which can't happen). If a number appears thrice, then all others appear exactly once : this gives one case. If one number appears twice, so must exactly one other number : this gives another case. But one of the above must happen : this gives the two cases of the second (and correct) solution.

---

Problem 2

Your approach is correct. The other approach seems to be of a different question : counting the ways in which at least one and at least one two occurs.