Probability of 6 cards summing to less than 20

I have cards with values $2, 3, 4, 5, 6, 7, 8.$ Five cards with each value. What's the formula to calculate the probability of randomly picking $6$ cards and having their values sum to less than $20$? (Cards are drawn without replacement)

Thanks!

Solution 1:

For denominator: If there are $5$ cards from each value ,then there are $35$ cards in total.The number of selecting $6$ cards without replacement is $\binom{35}{6}$

For numerator: We want to find the events where the sum of these $6$ cards is less than or equal to $20$.To solve this , i will use generating functions such that

• Generating functions of value $2's$: $$1+\binom{5}{1}x^2a+\binom{5}{2}x^4a^2+\binom{5}{3}x^6a^3 + \binom{5}{4}x^8a^4+ \binom{5}{5}x^{10}a^5$$

Let me explain what the foregoing expression means.We know that there are $5$ cards of value $2$ , then for example lets think $\binom{5}{3}x^6a^3$ , the binomial coefficient means selecting $3$ cards of value $2$ ,the exponential of $x^6$ means the sum of these $2$ cards of value $2$ , the exponential of $a^3$ means the number of cards. The first term $1$ means that we do not select from that card , you can see the result such that $\binom{5}{0}x^0a^0 =1$

• Generating functions of value $3's$: $$1+\binom{5}{1}x^3a+\binom{5}{2}x^6a^2+\binom{5}{3}x^9a^3 + \binom{5}{4}x^{12}a^4+ \binom{5}{5}x^{15}a^5$$

• Generating functions of value $4's$: $$1+\binom{5}{1}x^4a+\binom{5}{2}x^8a^2+\binom{5}{3}x^{12}a^3 + \binom{5}{4}x^{16}a^4+ \binom{5}{5}x^{20}a^5$$

• Generating functions of value $5's$: $$1+\binom{5}{1}x^5a+\binom{5}{2}x^{10}a^2+\binom{5}{3}x^{15}a^3 + \binom{5}{4}x^{20}a^4+ \binom{5}{5}x^{25}a^5$$

• Generating functions of value $6's$: $$1+\binom{5}{1}x^6a+\binom{5}{2}x^{12}a^2+\binom{5}{3}x^{18}a^3 + \binom{5}{4}x^{24}a^4+ \binom{5}{5}x^{30}a^5$$

• Generating functions of value $7's$: $$1+\binom{5}{1}x^7a+\binom{5}{2}x^{14}a^2+\binom{5}{3}x^{21}a^3 + \binom{5}{4}x^{28}a^4+ \binom{5}{5}x^{35}a^5$$

• Generating functions of value $8's$: $$1+\binom{5}{1}x^8a+\binom{5}{2}x^{16}a^2+\binom{5}{3}x^{24}a^3 + \binom{5}{4}x^{32}a^4+ \binom{5}{5}x^{40}a^5$$

Now , we should find the expansion of these generating functions , however realize that we do not need to include the variables of $x's$ whose exponential is greater than $20$ because of the restriction.When we find the expansion ,we must look at the coefficeints of such variables : $$\alpha x^ma^6$$ where $\alpha$ is the coefficient of that variable , $m$ is the number less than or equal to $20$ , $a^6$ means that we used $6$ cards.Then , $$[x^ma^6]\color{blue}{\bigg(}1+\binom{5}{1}x^2a+\binom{5}{2}x^4a^2+\binom{5}{3}x^6a^3 + \binom{5}{4}x^8a^4+ \binom{5}{5}x^{10}a^5\color{blue}{\bigg)}\color{red}{\bigg(}1+\binom{5}{1}x^3a+\binom{5}{2}x^6a^2+\binom{5}{3}x^9a^3 + \binom{5}{4}x^{12}a^4+ \binom{5}{5}x^{15}a^5\color{red}{\bigg)}\color{blue}{\bigg(}1+\binom{5}{1}x^4a+\binom{5}{2}x^8a^2+\binom{5}{3}x^{12}a^3 + \binom{5}{4}x^{16}a^4+ \binom{5}{5}x^{20}a^5\color{blue}{\bigg)}\color{red}{\bigg(}(1+\binom{5}{1}x^5a+\binom{5}{2}x^{10}a^2+\binom{5}{3}x^{15}a^3 + \binom{5}{4}x^{20}a^4\color{red}{\bigg)}\bigg(1+\binom{5}{1}x^6a+\binom{5}{2}x^{12}a^2+\binom{5}{3}x^{18}a^3\bigg)\bigg(1+\binom{5}{1}x^7a+\binom{5}{2}x^{14}a^2\bigg)\color{blue}{\bigg(}(1+\binom{5}{1}x^8a+\binom{5}{2}x^{16}a^2 \color{blue}{\bigg)}$$

After you find the satisfied coefficients , just sum them and divide by $C(35,6)$

I recommend you to use solfware to calculate the expansion , i tried to write it wolfram-alpha but it is too long for it.I think mathematica can handle it.

Solution 2:

This is the generating function approach already described by Bulbasaur's post. I use the Maxima CAS to do the calculations with the polynomials.

(%i1) e1:prod((1+y*x^i)^5,i,2,8),expand$
(%i2) e2:coeff(e1,y^6)$
(%i3) e3:e2*sum(x^i,i,0,20),expand$
(%i4) e4:coeff(e3,x^19);
(%o4)                                13815
(%i5) e5:e2,x=1,y=1;
(%o5)                               1623160
(%i6) e4/e5, numer;
(%o6)                        0.008511175731289584

(%i): The generating function with variable x and y is assigned to e1. prod is the product of the expression where I runs for 2 to 8. expandactually multiplies out all expressions and powers. This takes about 20 seconds on my notebook The $ ad the end of the expression suppresses the output of the result. This makes sense because i is a sum of more than 1000 terms of the form $ax^by^c$ $c$ is the number of cards drawn, $b$ is the sum of the values of these cards and the $a$ is the number of possibilities to get these $b$ and $c$.

(%i2): We are interested in the event that $6$ cards are drawn. So the coefficient of the $y^6$ is extracted and assigned to $e2$. This is a polynomial in $x$. The exponents are the sum of the values of the six cards drawn, the coefficients i the number of possibilities to draw 6 catds with this sum. we are interested only in the number of possibilities to achive a sum $\le 19$. There are differrent ways to calculate this. One is to divide $e2$ by $x^20$ and calculate the remainder, whisch is a polynomail of degree $19$. The sum of the coefficients of this polynomial is the requested number. It can be calculated by substituting $x$ by $1$ in this polynomial. A different way is the following. Such a sum of six cards that sum up to a value $\le 19$ can be viewed as a sum of $6$ casrd an an additional number, such that the sum of this seven numbers is $19$. This seventh number is a number between $0$ and $19$. We use this method.

(%i3): we multiply the polynomial $e2$, that shows us what values can be achieved by drawing 6 cards, by the dummy polynomial $1+x+x^2+x^3+...+x^{19}$ that represent the difference of the $19$ and the sum of the $6$ cards.

(%i4): e4 is now the coefficient of $x^{19}$. SO we extract this from the polynomial abd get 13815 that is show in the output line `(%o4)$.

(%i5): We callculate the number of all possibilities to draw 6 cards.

(%i6): we calculate the probability. numer forces the program to print a floatingpoint number instaad of a fraction.

We see that this rounded result is equal to the approximation of mjqxxxx's solution.

So is the usage of a CAS system like Maxima or Mathematica necessary if one uses generating functions with a lot of powers? Surprisingly not.

On can use a calculator that can work with arbitrary length integers to mimic such polynomial calculations if only positive coefficients are involved. For example: $$(x^2+3x+1)(2x^2+7x+5)=2 x^4+13x^3+28x^2+22x+5$$ the coefficient of $x^2$ of the product is $22$ If we substitute $100$ for $x$ in this equation, we get $$ 10301 \cdot 20705 = 213282205$$ And from the result on the left side we can directly extract the coefficients again $$2|13|28|22|05$$ This works, as long as we choose the value for $x$ larger than all of our coefficients. So let's calculate our numbers again. We use python that has implemented arbitrary integer aritmethics. The following program mimics our Maxima program. We substitute $x$ by $10^{13}$ because each coefficients of $e1$ is smaller as the sum of the coefficients of $e1$ and we get the sum of the coefficients of $e1$ by substituting $1$ of $x$, so it is $$\prod_{i=2}^8((1+yx^i)^5 = ((1+1)^5)^7<10^{11}$$

The highest power of $x$ is $40$, so we choose $$y=(10^{11})^{41}$$

x=10**11
y=x**41
e1=1
for i in [2,3,4,5,6,7,8]:
    e1*=(1+y*x**i)**5
e2=((e1%(y**7))//(y**6))

s=0
for i in range(21): # this means i in [0,1,2,3,...20]
    s+=x**i
e3=e2*s
e4=e3%(x**20)//(x**19)
print(e4)

which outputs 13815 as expected.

Solution 3:

To get a decent approximation, since the number of cards is large, consider the law of large numbers. The mean of the values is clearly $5$, and the variance is $70/17\approx 4.118$. So the sum of six randomly chosen cards should be $30 \pm \sqrt{6}\sqrt{4.118} = 30\pm 4.971$. Since $19 = 30 - 2.213 \times \sqrt{6}\sqrt{4.118}$, the Z-score is $-2.213$, and the corresponding probability (of a smaller sum) is about $0.013$.

Simulating $10^7$ draws yields $85530$ hits, so the real probability is more like $0.0086$. The estimate is off by maybe $40\%$; so the order of magnitude is correct, but not much better than that.

Also, an exact calculation yields a probability of $$p=\frac{2763}{324632}\approx 0.0085112.$$