|
|
| Line 1: |
Line 1: |
| | ==The Pot Method== | | ==The Pot Method== |
| | | | |
| − | The Pot Method is a double-counting method used to evaluate series with binomial coefficients, especially those with a binomial coefficient and another term in terms of the dummy variable. | + | The Pot Method is a double-counting method used to evaluate series with binomial coefficients, especially those with a binomial coefficient and another term in terms of the dummy variable. |
| − | | |
| − | ==Scenario==
| |
| − | | |
| − | Consider the following scenario:
| |
| − | | |
| − | You have 100 red marbles and 100 blue marbles in a pot, throughly mixed up. If you draw 100 marbles, what is the expected number of blue marbles?
| |
| − | | |
| − | We know that <math>E(\text{Red Marbles}) = E(\text{Blue Marbles})</math>, by symmetry. Also, using some common sense, it also makes sense that <math>E(\text{Red Marbles})+E(\text{Blue Marbles})=100</math>, so <math>E(\text{Blue Marbles}) = 50</math>.
| |
| − | | |
| − | The other way to count this expected value is case-by-case based on the number of blue marbles.
| |
| − | | |
| − | k Blue Marbles: The number of blue marbles is k. The number of ways to do this is the number of ways is <math>\dbinom{100}{k} \cdot \dbinom{100}{100-k} = \dbinom{100}{k}^2</math>, as we want to choose <math>k</math> blue marbles and <math>100-k</math> red ones. The total number of ways to do this is <math>\dbinom{200}{100}</math>, so the expected value for this case is <math>\frac{1}{\dbinom{200}{100}} \cdot \dbinom{100}{k}^2</math>.
| |
| − | | |
| − | Summing from <math>k = 0</math> to <math>k=100</math>, we get that
| |
| − | <cmath> E(\text{Blue Marbles}) = \frac{1}{\dbinom{200}{100}} \cdot \sum_{k=0}^{100} \binom{100}{k}^2k = 50 \Rightarrow \sum_{k=0}^{100} \dbinom{100}{k}^2k = 50 \cdot \dbinom{200}{100}.</cmath>
| |
| − | | |
| − | Sure enough, WA confirms this is true.
| |
| − | | |
| − | What about if we have 30 red marbles, 30 blue marbles, 30 green marbles, we pick 30, what is the expected number of blue ones?
| |
| − | | |
| − | Similarly, we find that <math>E(\text{Blue Marbles}) = 10</math>. Using our double counting approach, though:
| |
| − | | |
| − | k Blue Marbles: The number of blue marbles is k. We could have either <math>0</math> red, <math>30-k</math> green to <math>30-k</math> red, <math>0</math> green. There are <math>\dbinom{30}{k}</math> ways to choose the blue marbles. Essentially, finding the total way for <math>k</math> blue marbles is
| |
| − | <cmath>\sum_{j=0}^{30-k} \dbinom{30}{j}\dbinom{30}{30-k-j}\dbinom{30}{k}</cmath>
| |
| − | Using Vandermonde's identity, this is equal to <math>\dbinom{60}{30-k}\dbinom{60}{k}</math>. The total way is <math>\dbinom{90}{30}</math>, so our expected value for this case is <math>\frac{1}{\dbinom{90}{30}} \cdot \dbinom{60}{30-k}k\dbinom{60}{k}</math>.
| |
| − | Thus, summing from <math>k=0</math> to <math>k=30</math>, we get
| |
| − | <cmath>E(\text{Blue Marbles}) = \frac{1}{\dbinom{90}{30}} \cdot \sum_{k=0}^{30} \dbinom{60}{30-k}\dbinom{60}{k}k = 10 \Rightarrow \sum_{k=0}^{30} \dbinom{60}{30-k}\dbinom{60}{k}k = 10 \cdot \dbinom{90}{30}.</cmath>
| |
| − | | |
| − | WA confirms this.
| |
