Vandermone's SRSWR | MStat 2017 PSB Problem 3

This is a beautiful problem form ISI MStat 2017 PSB Problem 3, where we use the basics of Bijection principle and Vandermone's identity to solve this problem.

Problem

Consider an urn containing 5 red, 5 black, and 10 white balls. If balls are drawn without replacement from the urn, calculate the probability that in the first 7 draws, at least one ball of each color is drawn.

Prerequisites

• Algebrify the problem
• Vandermone's Identity $${{n_{1}+\cdots+n_{p}} \choose m} = \sum_{k_{1}+\cdots+k_{p}=m} {n_{1} \choose k_{1}} \times {n_{2} \choose k_{2}} \times \cdots \times {n_{p} \choose k_{p}}$$

• Bijection Principle

Solution

It may give you the intuition, there is atleast in the problem, so let's do complementing counting. Okay! I suggest you to travel that path to help you realize the complexity of that approach.

Nevertheless, let's algebrify the problem.

You want to select \(x_1\) red balls, \(x_2\) blue balls, and \(x_3\) white balls so that \(x_1 + x_2 + x_3 = 7\).

Now, \( 1 \leq x_1 \leq 5\), \(1 \leq x_2 \leq 5\) and \(1 \leq x_3 \leq 10\) represents our desired scenario.

\( 0 \leq x_1 \leq 5\), \(0 \leq x_2 \leq 5\) and \( 0 \leq x_3 \leq 10\) denotes total number of cases.

Now, for each such triplet (\(x_1, x_2, x_3\)) of the number of balls of each colour we have selected, we can select them in \( { 5 \choose x_1} \times {5 \choose x_2 } \times {10 \choose x_3} \).

Let \( P = \{ (x_1, x_2, x_3) | x_1 + x_2 + x_3 = 7, 0 \leq x_1 \leq 5, 0 \leq x_2 \leq 5, 0 \leq x_3 \leq 10 \} \).

Total Number of Ways we can select the 7 balls =

$$ \sum_{(x_1, x_2, x_3) \in P} { 5 \choose x_1} \times {5 \choose x_2 } \times {10 \choose x_3} = { {5 + 5 + 10} \choose { x_1 + x_2+ x_3} } = { {5 + 5 + 10} \choose {7} }$$

\( Q = \{ (x_1, x_2, x_3) | x_1 + x_2 + x_3 = 7, 1 \leq x_1 \leq 5, 1 \leq x_2 \leq 5, 1 \leq x_3 \leq 10 \} \).

Total Number of Ways we can select the 7 balls such that at least one ball of each color is drawn =

$$ \sum_{(x_1, x_2, x_3) \in Q} { 5 \choose x_1} \times {5 \choose x_2 } \times {10 \choose x_3}$$

Let, \( R = \{ (z_1, z_2, z_3) | z_1 + z_2 + z_3 = 4, 0 \leq z_1 \leq 4, 0 \leq z_2 \leq 4, 0 \leq z_3 \leq 9 \} \).

Observe that \(Q\) has a bijection with \(R\). \( x_i = z_i +1\).

Total Number of Ways we can select the 7 balls such that at least one ball of each color is drawn =

$$ \sum_{(x_1, x_2, x_3) \in R} { 4 \choose z_1} \times {4 \choose z_2 } \times {9 \choose z_3} = { {4 + 4 + 9} \choose { z_1 + z_2+ z_3} } = { {4 + 4 + 9} \choose {4} }$$

Exercises

• Prove the Vandermone's Identity.
• Find the Probability.
• Generalize the problem to general numbers and prove it.
• Generalize the problem where the lower bounds of \(x_i\) are \(m_i\).
• What if there are upper bounds on \((x_1, x_2, x_3)\)? [ Hint: Generating Functions ].

Stay Tuned! Stay Blessed!