Calculating the Probability of Getting 13 Points in a 13-Card Hand in Bridge

[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 I am stuck:

I can calculate the odds for certain combinations of cards, but i don't 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 wouldn't 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.

 

[Adeimantus]

This Wikipedia page on partitions of numbers might help you get started:

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:

...More generally, the generating function for the partitions of n into numbers from a set A can be found by taking only those terms in the product where k is an element of A.

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:

Similar techniques can be employed to establish, for example, the following equalities:

The number of partitions of n into no more than k parts is the same as the number of partitions of n into parts no larger than k.
...

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...

 

[Adeimantus]

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

 

[timon]

thanks for the help but i still don't get it. :(

 

[Adeimantus]

thanks for the help but i still don't get it. :(

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?

 

[timon]

I did that and got 13 different combinations.
If that's 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.

 

[Adeimantus]

I did that and got 13 different combinations.

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.

If that's 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

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?

 

[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

 

[CRGreathouse]

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

36. what now? :p

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

 

[Adeimantus]

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 AKQQJJ?
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.

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.

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

36. what now? :p

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?

 

[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)

 

[Adeimantus]

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

Correct!

this is what i get now:

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 K Q Q J J
12. A Q Q Q Q J
13. A Q Q Q J J J
14. K K K K J
15. K K K Q Q
16. K K K Q J J
17. K K K J J J J
18. K K Q Q Q J
19. K K Q Q J J J
20. K Q Q Q Q J J
21. K Q Q Q J J J J

still only 20 though :-(

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.

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

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

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.

 

[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 don't even know what a polynomial is.. or i don't know the english word :p

 

[Adeimantus]

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 don't even know what a polynomial is.. or i don't know the english word :p

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?

 

[timon]

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

 

[Adeimantus]

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

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.

 

[timon]

doublepost

 

[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.

 

[bpet]

(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)

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%.

 

[timon]

6.9%? are you sure?

 

[Adeimantus]

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%.

Okay, I get the same thing (0.069143 to be exact). But I'm too dumb to understand how your method works. Can you explain it a little bit? timon and I both will learn something

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.
T 02:55 AM

You are welcome . 7.1% is so close to 6.9% that I'm guessing the difference comes from roundoff errors. Adding, multiplying, and dividing lots of very large numbers, as you must do in this problem, can cause small rounding errors to accumulate.

For the poker question, you're right, it's not as simple as squaring the probability of three-of-a-kind for one player. It sounds like you are describing Hold'em poker, with five shared face-up cards? I'm not sure how to calculate that probability. I'll think about it. Maybe someone else here knows how...

 

[timon]

yeah, texas hold 'm.

 

[bpet]

Okay, I get the same thing (0.069143 to be exact). But I'm too dumb to understand how your method works. Can you explain it a little bit? timon and I both will learn something

Sure :)

Each card is represented by factor in the polynomial. Each possibility is a term (x^n)*(y^m) where n is the number of points the player gets and m is the number of cards the player gets. For example the ace of spades is either dealt to the player (x^4*y^1) or dealt to somebody else (x^0*y^0), so its polynomial is (1+x^4*y). As you multiply the factors, all the possibilities combine and the coefficients keep track of the number of different ways that possibility can be obtained. In the final product of 52 factors we only want the 13-card hands so take the terms that include y^13, and you're left with a polynomial in x which gives the distribution of points in the player's hand.

To convince yourself it works, maybe try the algebra for a four-card deck between two players.

HTH

 

[Adeimantus]

Sure :)

Each card is represented by factor in the polynomial. Each possibility is a term (x^n)*(y^m) where n is the number of points the player gets and m is the number of cards the player gets. For example the ace of spades is either dealt to the player (x^4*y^1) or dealt to somebody else (x^0*y^0), so its polynomial is (1+x^4*y). As you multiply the factors, all the possibilities combine and the coefficients keep track of the number of different ways that possibility can be obtained. In the final product of 52 factors we only want the 13-card hands so take the terms that include y^13, and you're left with a polynomial in x which gives the distribution of points in the player's hand.

To convince yourself it works, maybe try the algebra for a four-card deck between two players.

HTH

Ah, that is very cool. Thanks. I found it helped me to see it by expanding each factor using the binomial theorem:

$$(1+y)^{36}(1+yx)^4(1+yx^2)^4+(1+yx^3)^4(1+yx^4)^4 = \sum_{r=0}^{36}^{36}C_r y^r \sum_{j=0}^4^4C_j y^jx^j \sum_{q=0}^4^4C_qy^qx^{2q} \sum_{k=0}^4^4C_k y^kx^{3k} \sum_{a=0}^4^4C_a y^ax^{4a}$$

timon:
you might want to start a new thread to see if someone can answer the poker question. It seems like a difficult calculation to me. If you know how to do a computer simulation of it, that might be easier.

 

[mphil]

is dihedral is solvable

 

[TVP45]

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 I am stuck:

I can calculate the odds for certain combinations of cards, but i don't 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 wouldn't 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.

If you're sitting west, there's almost zero chance.