Probabilaty - bridge game

1. Feb 2, 2009

timon

hi everyone

Problem:

In (a simplified version of) bridge:
each player is dealt 13 cards out of a full 52 card deck.
Where an ace is worth 4 points;
a king 3 points;
a queen 2 points;
and a jack 1 point.
The rest of the cards (2-10) are worth 0 points.
Question: what is the chance of one player getting exactly 13 points with his 13 card hand?

Where im stuck:

I can calculate the odds for certain combinations of cards, but i dont know how to calculate the amount of possible ways to get 13 points out of 13 cards with the given score table.(i filled a few pages trying stuff, but its in dutch so wouldnt be of much use to post - plus i didnt get anywhere)

Any help is very much apreciated, i need to hand in a paper on this next week.

Last edited: Feb 2, 2009
2. Feb 3, 2009

http://en.wikipedia.org/wiki/Ferrers_diagram

You are trying to find a certain kind of restricted partition of 13....in particular, one that involves numbers no greater than 4 (this is not quite right. See my next post). I've never actually done anything with partitions myself, so I can offer only limited help. Surely there are some number theory wizards here who can offer more help if needed. My guess is that you should use the generating function (see above Wiki article) to help you find how many partitions there are. Note that you will be using a restricted version of the generating function, as the wikipedia page explains:

So the restricted generating function would be

$$\sum_{n=0}^{\infty}p(n: \mbox{using numbers less than or equal to 4})x^n = \prod_{k=1}^{4}\left( \frac{1}{1-x^k} \right)$$
This formula assumes you have an unlimited number of Aces, Kings, Queens, and Jacks in the deck, which is incorrect.

I think you just expand it out and collect all terms of order x^13 and the coefficient of that term is your answer. Alternatively, if you have access to a symbolic math package like Mathematica, you could evaluate the 13th derivative of the generating function at x=0, and divide the result by 13 factorial.

To actually find the partitions themselves (assuming you know how many there are to look for), I'm guessing the Ferrers diagrams will help you. From the Wikipedia article:

Also, you might find it helpful to try a simpler version of the problem first, just to get the hang of it: find the probability that a 5 card hand totals exactly 5 points. Good luck!

edit: I had forgotten the summation symbol in the left side of the formula...

Last edited: Feb 3, 2009
3. Feb 3, 2009

Oh darn! I forgot you only have 4 each of aces, kings, queens, and jacks to choose from . Your counting problem is trickier than I thought. The generating function formula I gave above assumes you have as many as you need of each, so it is not suitable for your problem. Still, maybe that wikipedia article will give you some ideas.

edit: well, it looks like you can use an even more "restricted" version of the generating function that accounts for the fact that there are only 4 aces, 4 kings, 4 queens, and 4 jacks to choose from. When you figure out the generating function, you might want to use this online Mathematica tool to save you some algebra:

http://www.hostsrv.com/webmab/app1/MSP/quickmath/02/pageGenerate?site=quickmath&s1=algebra&s2=expand&s3=basic [Broken]

Last edited by a moderator: May 4, 2017
4. Feb 5, 2009

timon

thanks for the help but i still dont get it. :(

5. Feb 5, 2009

After thinking some more, I think I was just making things more difficult than necessary. Sorry about that. A brute-force approach is probably more appropriate than a theoretical approach, such as trying to use generating functions. Try this instead: simply list the combinations of aces, kings, queens, and jacks in a systematic way that allows you to be sure you haven't skipped any that total to 13 points. Start with the hand that has the maximum number of aces and is worth 13 points: 3 Aces, 1 Jack, and the remainder are cards with face-values 2 through 10 which do not contribute to the total. Label this hand AAAJ. The ordering goes from left to right, and higher cards come before lower cards (as valued by the scoring A=4, K=3, Q=2, J=1). After AAAJ the next hand in order would be AAKQ. Since the rightmost card in AAAJ, a Jack, is the lowest card, you have go to the card before that, and Ace, and replace it with a King. This decreases the total to 12, so you replace the Jack with a Queen to bring the total back up to 13, giving AAKQ. To find the next hand, note that the rightmost card in AAKQ is a Queen. You replace it with a Jack, bringing the total down to 12, and now you have to add on another Jack to bring the total back up to 13, giving AAKJJ. Here are the first few hands in order:

1. AAAJ
2. AAKQ
3. AAKJJ
4. AAQQJ
5. AAQJJJ
.....

Do you see the pattern?

6. Feb 7, 2009

timon

I did that and got 13 different combinations.
If thats correct the next question is: how do i calculate how many different ways of ordering the cards are there for each of these combinations?

for example for AAAJ + 9 other cards

thanks again.

7. Feb 7, 2009

Actually, there are 21. I'll list a few more to help you check your list. It's easy to miss some of them. In fact, I missed some while trying to type up this list, but it should be correct now.

1. AAAJ
2. AAKQ
3. AAKJJ
4. AAQQJ
5. AAQJJJ
6. AKKK
7. AKKQJ
8. AKKJJJ
9. AKQQQ
10. AKQQJJ
11. AKQJJJJ
12. AQQQQJ
13. AQQQJJJ
14. KKKKJ

.......

21. KQQQJJJJ

It is similar to alphabetical ordering, except that the value of the card is what determines order rather than a letter's place in the alphabet. Also, you have two constraints: you can't use more than four of each kind of card, and the points must add to 13. See if you can fill in the remaining ones.

Well, the exact order of the hand, such as 2556AA9J3744A, does not matter. All that matters is that you have three Aces, one Jack, and 9 cards selected from those whose face-values are 2 through 10 and do not contribute to the point total. There are 4 Aces from which you choose 3, and 4 Jacks from which you choose 1. How many cards have face-value 2-10, from which you choose 9?

Last edited: Feb 7, 2009
8. Feb 9, 2009

timon

1. A A A J
2. A A K Q
3. A A K J J
4. A A Q Q J
5. A A Q J J J
6. A K K K
7. A K K Q J
8. A K K J J J
9. A K Q J J J J
10. A K Q Q Q
11. A Q Q Q J J J
12. A Q Q Q Q J
13. A Q Q Q J J
14. K K K K J
15. K K K Q Q
16. K K Q Q Q J
17. K K Q Q J J J
18. K Q Q Q Q J J
19. K Q Q Q J J J J
20. Q Q Q Q Q J J J

you are right, i was not done yet. this is what i get now - 20 combinations.

How many cards have face-value 2-10, from which you choose 9?

36. what now? :p

Last edited: Feb 9, 2009
9. Feb 9, 2009

CRGreathouse

That sounds suspiciously like "36 choose 9", which was probably an intentional hint.

10. Feb 9, 2009

OK, you are almost there. QQQQQJJJ has too many queens, so you are missing at least two combinations. Your #13 does not add up to 13 points, unless you meant AKQQJJ. Starting with #9 you are getting out of order. The order of the list is essential because it helps you find what is missing. After #14 you have the order right, but you skipped two combinations. You obviously have the idea, you just need to go through the list again carefully.

CRGreathouse was correct...I was trying to hint at binomial coefficients, such as "4 choose 3" and "36 choose 9". As a warmup exercise to calculating the probability of a particular hand such as AAAJ, try this:

A bag of fruit contains 2 apples, 2 oranges, and 4 bananas (and nothing else). You randomly draw four pieces of fruit from the bag. What is the probability that you draw 1 orange and 3 bananas?

11. Feb 12, 2009

timon

for the fruit : (2 nCr 1 * 4 nCr 3) / (8 nCr 4)

this is what i get now:

A A A J
A A K Q
A A K J J
A A Q Q J
A A Q J J J
A K K K
A K K Q J
A K K J J J
A K Q J J J J
A K Q Q Q
A K Q Q J J
A Q Q Q Q J
A Q Q Q J J J
K K K K J
K K K Q J J
K K K J J J J
K K Q Q Q J
K K Q Q J J J
K Q Q Q Q J J
K Q Q Q J J J J

still only 20 though :-(

for AAAJ would the calculation be something like this:
(4 nCr 3) * (4 nCr 1) * (36 nCr 9) / (52 nCr 13)

Last edited: Feb 12, 2009
12. Feb 12, 2009

Correct!

You skipped #15, KKKQQ. Also, if you want the list to be ordered consistently, you should rearrange #9 through #11 to be:

9. AKQQQ
10. AKQQJJ
11. AKQJJJJ

You see why, right? You followed that ordering in the rest of the list, so it looks like you understand it, even though my explanation of it wasn't that great.

You've got it! Now you just do that for the other 20 hands and add up the results.

edit: Use this website (which has online Mathematica tools)

http://www.hostsrv.com/webmab/app1/MSP/quickmath/02/pageGenerate?site=quickmath&s1=algebra&s2=expand&s3=basic [Broken]

to expand this polynomial:

(1+x+x^2+x^3+x^4)*(1+x^2+x^4+x^6+x^8)*(1+x^3+x^6+x^9+x^12)*(1+x^4+x^8+x^12+x^16)

Look at the coefficient of x^13 in the result it gives.

Last edited by a moderator: May 4, 2017
13. Feb 13, 2009

timon

i have mathematica on my laptop.. but what does it mean?
$$1+x+2 x^2+3 x^3+5 x^4+5 x^5+8 x^6+9 x^7+12 x^8+13 x^9+16 x^{10}+17 \\ x^{11}+21 x^{12}+21 x^{13}+24 x^{14}+25 x^{15}+28 x^{16}+27 x^{17}+30 \\ x^{18}+29 x^{19}+31 x^{20}+29 x^{21}+30 x^{22}+27 x^{23}+28 x^{24}+25 \\ x^{25}+24 x^{26}+21 x^{27}+21 x^{28}+17 x^{29}+16 x^{30}+13 x^{31}+12 \\ x^{32}+9 x^{33}+8 x^{34}+5 x^{35}+5 x^{36}+3 x^{37}+2 x^{38}+x^{39}+x^{40} \\$$

i dont even know what a polynomial is.. or i dont know the english word :p

Last edited: Feb 13, 2009
14. Feb 13, 2009

A polynomial (in one variable, say x) is an expression made by adding up powers x, which can have real number coefficients. 1-x+6x^3 is a polynomial of order 3, for instance. I think polynomial means roughly "many terms", so maybe you recognize the Dutch word for that.

In the result from Mathematica, the coefficient of x^13 is 21. Those numbers should look familiar. Look again at the factored expression

(1+x+x^2+x^3+x^4)*(1+x^2+x^4+x^6+x^8)*(1+x^3+x^6+x ^9+x^12)*(1+x^4+x^8+x^12+x^16)

In the first factor, the exponents of x are multiples of 1, namely 0 through 4. In the second factor, the exponents are multiples of 2: 0*2 through 4*2. The third factor has multiples of 3, and the fourth factor has multiples of 4. The coefficient of 21 in the expanded expression represents the number of ways you can get x^13 by multiplying together one term from the first factor, a term from the second factor, a term from the third factor, and a term from the fourth factor. see where this is going?

15. Feb 17, 2009

timon

hmm... im sortoff getting it, but i dont think i would be able to explain it to someone. could you give a simpler example? im not sure this would be of any use ifor my question, since i wouldnt know the chance for each of the possible combinations, only how many combinations there are?

16. Feb 17, 2009

It's true that you do not need this extra stuff to answer your question. You were able to calculate the probability that a 13 card hand totals to exactly 13 points, right?

The purpose of multiplying out the polynomial was to show there is a way of double checking that there are exactly 21 combinations of A, K, Q, J that total 13 points and use no more than 4 of each rank. When you are trying to generate all the combinations, it is helpful to know that you are looking for 21. That way, if you make a list and you only have 19, you know you are missing two.

If, for example, you wanted to know how many combinations of Q and J total to 6 points, you would expand the following polynomial

$$(1+x+x^2+x^3+x^4)(1+x^2+x^4+x^6+x^8) = 1+x+2x^2+2x^3+3x^4+2x^5+3x^6+2x^7+3x^8+2x^9+2x^{10}+x^{11}+x^{12}$$

The coefficient of x^6 is 3, so there are 3 combinations of Q and J that total 6 points:

QQQ
QQJJ
QJJJJ

Now that list is easy enough that you don't need to double-check that you have the right number of combinations. But as we saw with your problem, it's much harder to be sure you have all the combinations of A,K,Q,J that total to 13.

Think of the factor (1+x+x^2+x^3+x^4) as representing ( 0 jacks, 1 jacks, 2 jacks, 3 jacks, 4 jacks) and the factor (1+x^2+x^4+x^6+x^8) as representing ( 0 queens, 1 queen, 2 queens, 3 queens, 4 queens ). The exponents in the first factor are mutliples of 1, the value of the Jack. The exponents in the second factor are multiples of 2, the value of the Queen.

QQQ corresponds to 1*x^6 = x^(0*1) * x^(3*2)
QQJJ corresponds to x^2 * x^4 = x^(2*1) * x^(2*2)
QJJJJ corresponds to x^4 * x^2 = x^(4*1) * x^(1*2)

These are all the ways you can get x^6 by taking one term from the first factor and multiplying it by a term from the second factor.

17. Feb 19, 2009

timon

doublepost

Last edited: Feb 19, 2009
18. Feb 19, 2009

timon

Ah! I think I'm getting it now. I will probably be able to use this so thanks again. :-)

The answer to my original question was 7.1 %.

Another question now: What are the odds that two players get three-of-a-kind in a game of poker?
My first idea was to square the chance for three-of-a-kind for one player, but that doesn't seem right to me since it doesn't take the shared cards on the table into account.

19. Feb 19, 2009

bpet

To keep track of the number of cards in the player's hand, you might need to include a second variable y in the polynomial. The polynomial would be

P=((1+y)^9*(1+y*x)*(1+y*x^2)*(1+y*x^3)*(1+y*x^4))^4

Then take the coefficient of y^13 to get a polynomial P1(x) for the distribution of points when the player has 13 cards. Then divide the coefficient of x^13 by the sum of the coefficients to get your answer, about 6.9%.

20. Feb 19, 2009

timon

6.9%? are you sure?