Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "The Pot Method"

(Created page with "==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 ter...")
 
(I am restoring what was here earlier.)
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
==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==
 
  
 +
Scenario
 
Consider the following 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?
 
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>.
+
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>.  
+
The other way to count this expected value is case-by-case based on the number of blue marbles.
  
−
Summing from <math>k = 0</math> to <math>k=100</math>, we get that
+
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>.
−
<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.  
+
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?
 
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?
Line 24: Line 19:
 
Similarly, we find that <math>E(\text{Blue Marbles}) = 10</math>. Using our double counting approach, though:
 
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  
+
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>
−
<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.
 
WA confirms this.

Latest revision as of 18:10, 4 April 2019

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 $E(\text{Red Marbles}) = E(\text{Blue Marbles})$, by symmetry. Also, using some common sense, it also makes sense that $E(\text{Red Marbles})+E(\text{Blue Marbles})=100$, so $E(\text{Blue Marbles}) = 50$.

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 $\dbinom{100}{k} \cdot \dbinom{100}{100-k} = \dbinom{100}{k}^2$, as we want to choose $k$ blue marbles and $100-k$ red ones. The total number of ways to do this is $\dbinom{200}{100}$, so the expected value for this case is $\frac{1}{\dbinom{200}{100}} \cdot \dbinom{100}{k}^2$.

Summing from $k = 0$ to $k=100$, we get that \[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}.\] 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 $E(\text{Blue Marbles}) = 10$. Using our double counting approach, though:

k Blue Marbles: The number of blue marbles is k. We could have either $0$ red, $30-k$ green to $30-k$ red, $0$ green. There are $\dbinom{30}{k}$ ways to choose the blue marbles. Essentially, finding the total way for $k$ blue marbles is \[\sum_{j=0}^{30-k} \dbinom{30}{j}\dbinom{30}{30-k-j}\dbinom{30}{k}\] Using Vandermonde's identity, this is equal to $\dbinom{60}{30-k}\dbinom{60}{k}$. The total way is $\dbinom{90}{30}$, so our expected value for this case is $\frac{1}{\dbinom{90}{30}} \cdot \dbinom{60}{30-k}k\dbinom{60}{k}$. Thus, summing from $k=0$ to $k=30$, we get \[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}.\] WA confirms this.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=The_Pot_Method&oldid=105125"