Combination example: 9 card hands
Thinking about how many ways we can construct a hand of 9 cards. Created by Sal Khan and Monterey Institute for Technology and Education.
Want to join the conversation?
- What about the suits? Do they have any relevance in this? Would we multiply the final result shown by 4?(27 votes)
- Like the other answers say the suits are irrelevant, but you can't help but think they're somehow relevant, so I think it's also a red herring : https://en.wikipedia.org/wiki/Red_herring and it's a skill to fish them out (pun intended)(14 votes)
- and then if i do care about the order, i just don't add the extra k! in the denominator, right?(21 votes)
- That's right. Notice that if you had k people out of order and you cared about ordering them, you could choose the first person in k ways, the second person in k-1 ways, and all the way down to the last person being the only person left, so it works out that there were k! ways to sort them.(20 votes)
- Say a word has multiple letters repeating- like ARCHITECTURE- the R, C,E and T repeat. The practice questions only have one letter repeating like PLOP (P) or ERROR (R). How would you compute the number of distinct permutations you can get from the word ARCHITECTURE?(11 votes)
- You just need to divide by the number of combinations for each duplicate letter.
ARCHITECTURE has 12 letters with 2 Rs, 2 Cs, 2 Ts, and 2 Es so you have 12!/(2!*2!*2!*2!) = 29,937,600 permutations
Another example would be MISSISSIPPI, 11 letters with 4 Ss, 4 Is, and 2 Ps and 11!/(4!*4!*2!) = 34,650 arrangements.(19 votes)
- Why is it not 36P9?(11 votes)
- in 36P9 we would count a hand if the same cards in different order. however whatever order the cards come in, if they are the same, it will be the same hand. we would not want to count the same hand twice. hence order wont matter. so, we use 36C9. ie. we divide 36P9 with the number of different ways 9 things can be ordered (9!). hope i am right.(10 votes)
- how can i know that a particular question is permutation or combination(6 votes)
- In permutations, the order of the results matters.
- license plate number
- lottery number
- serial number
- phone number
- safe code
In combinations, the order does not matter.
- card games
- nominees for government office
- pizza toppings
In order to tell the difference, just ask yourself if the order of the results matters:
Yes? = permutation
No? = combination
Hope this helps!(14 votes)
- What if the denominator became 0 factorial?(5 votes)
- Why does dividing 36! by 9! make sense? I still don't understand why this formula give us the combination?
Sorry, I always ask these silly questions... T_T(3 votes)
- What Sal did can be written as: 36!/(27! * 9!)
- 36! is the number of ways 36 cards can be arranged.
- 27! is the number of ways the remaining 36 - 9 = 27 cards can be arranged. It makes sense, since you don't care about the arrangement of the cards you are not going to have in a 9-card hand.
- 9! is just the number of ways you can arrange your hand after picking the 9 cards. It makes sense, because if I gave you 9 cards, you can arrange them however you want (arrange them by color, by type of suit, correlatively, etc.), but all those arrangement you can make don't change the fact that they are still the same 9 cards I gave you before.
Permutations care about those arrangements you can make after receiving the cards (i.e, order matters), while combinations don't.(6 votes)
- This keeps coming up in the practice, and while I can answer it now due to repetition, I don't understand it. is there a formula (my brain likes formulas)? You need to put your reindeer, Jebediah, Lancer, Ezekiel, Gloopin, and Bloopin, in a single-file line to pull your sleigh. However, Lancer and Ezekiel are best friends, so you have to put them next to each other, or they won't fly.
How many ways can you arrange your reindeer?(4 votes)
- Think of the "best friends" as one unit/reindeer, then figure out how many ways there are to arrange four reindeer in a single-file line.
Here's the trick: remember how we pretended the two "best friends" were one reindeer unit? In each of those arrangements, either Lancer or Ezekiel can come first! And this gives you twice as many arrangements as you figured out in the first step.
So, multiply the number of arrangements x2 to get the final total.
Hope this helps!(2 votes)
- how do I calculate the number unique combinations if we have 4 letters (A,B,C and D) where AB is equal BA (similar to handshaking) and each letter by itself is a combination. The following shows all the acceptable combinations:
- Off-hand I don't recall any formula to do this. We basically just have to repeat the process for each number of letters that we're considering. So we'd say:
1 letter: 4 nCr 1 = 4
2 letters: 4 nCr 2 = 6
3 letters: 4 nCr 3 = 4
4 letters: 4 nCr 4 = 1(5 votes)
- One thing I wondered while doing the exercises is: why is n! / k! (n-k)! always resulting in an integer? I understand that it should in these problems but don't see how to prove it based on this formula.(3 votes)
- Well C= nPr/r! which is C= n!/r!(n-r)!.
Remember that n>r by definition. if n=r the n answer is 1! . So we know that r! divises n! (if n>r, n!/r! gives you an integer ex: 5!/3!= 5*4).
We also know that (n-r)! divises n! (if n>(n-r), n!/(n-r)! gives you an integer ex: 5!/(5-2)!= 5!/3!= 5*4)
We are almost done, since we know than n! is divisble by r! AND (n-r)!. There is a property in number theory that stats the following: if b divises a and c divises a then bc divises a.
(EDIT: this is only true when no prime divises bc in its reduced term. E.g bc< or equal to a.
Which is exactly what we have in the case of the combinatorics, n!>r!(n-r)!, we can proof this by induction.)
Induction: n!>or equal r!(n-r)! for n>or equal r ---> true i.e. 1!>or equal 1!(1-1)! =1
(n+1)!>r!(n+1-r)! <=> n!(n+1)>r!(n-r)!(n+1-r).
We now have to prove : (n+1)>(n+1-r) which is the case for every n>or equal to r.
So we can say that n!/r!(n-r!) will always result to be an integer if n is greater or equal to r.(2 votes)
A card game using 36 unique cards, four suits, diamonds, hearts, clubs and spades-- this should be spades, not spaces-- with cards numbered from 1 to 9 in each suit. A hand is chosen. A hand is a collection of 9 cards, which can be sorted however the player chooses. Fair enough. How many 9 card hands are possible? So let's think about it. There are 36 unique cards-- and I won't worry about, you know, there's nine numbers in each suit, and there are four suits, 4 times 9 is 36. But let's just think of the cards as being 1 through 36, and we're going to pick nine of them. So at first we'll say, well look, I have nine slots in my hand, right? 1, 2, 3, 4, 5, 6, 7, 8, 9. Right? I'm going to pick nine cards for my hand. And so for the very first card, how many possible cards can I pick from? Well, there's 36 unique cards, so for that first slot, there's 36. But then that's now part of my hand. Now for the second slot, how many will there be left to pick from? Well, I've already picked one, so there will only be 35 to pick from. And then for the third slot, 34, and then it just keeps going. Then 33 to pick from, 32, 31, 30, 29, and 28. So you might want to say that there are 36 times 35, times 34, times 33, times 32, times 31, times 30, times 29, times 28 possible hands. Now, this would be true if order mattered. This would be true if I have card 15 here. Maybe I have a-- let me put it here-- maybe I have a 9 of spades here, and then I have a bunch of cards. And maybe I have-- and that's one hand. And then I have another. So then I have cards one, two, three, four, five, six, seven, eight. I have eight other cards. Or maybe another hand is I have the eight cards, 1, 2, 3, 4, 5, 6, 7, 8, and then I have the 9 of spades. If we were thinking of these as two different hands, because we have the exact same cards, but they're in different order, then what I just calculated would make a lot of sense, because we did it based on order. But they're telling us that the cards can be sorted however the player chooses, so order doesn't matter. So we're overcounting. We're counting all of the different ways that the same number of cards can be arranged. So in order to not overcount, we have to divide this by the ways in which nine cards can be rearranged. So we have to divide this by the way nine cards can be rearranged. So how many ways can nine cards be rearranged? If I have nine cards and I'm going to pick one of nine to be in the first slot, well, that means I have 9 ways to put something in the first slot. Then in the second slot, I have 8 ways of putting a card in the second slot, because I took one to put it in the first, so I have 8 left. Then 7, then 6, then 5, then 4, then 3, then 2, then 1. That last slot, there's only going to be 1 card left to put in it. So this number right here, where you take 9 times 8, times 7, times 6, times 5, times 4, times 3, times 2, times 1, or 9-- you start with 9 and then you multiply it by every number less than 9. Every, I guess we could say, natural number less than 9. This is called 9 factorial, and you express it as an exclamation mark. So if we want to think about all of the different ways that we can have all of the different combinations for hands, this is the number of hands if we cared about the order, but then we want to divide by the number of ways we can order things so that we don't overcount. And this will be an answer and this will be the correct answer. Now this is a super, super duper large number. Let's figure out how large of a number this is. We have 36-- let me scroll to the left a little bit-- 36 times 35, times 34, times 33, times 32, times 31, times 30, times 29, times 28, divided by 9. Well, I can do it this way. I can put a parentheses-- divided by parentheses, 9 times 8, times 7, times 6, times 5, times 4, times 3, times 2, times 1. Now, hopefully the calculator can handle this. And it gave us this number, 94,143,280. Let me put this on the side, so I can read it. So this number right here gives us 94,143,280. So that's the answer for this problem. That there are 94,143,280 possible 9 card hands in this situation. Now, we kind of just worked through it. We reasoned our way through it. There is a formula for this that does essentially the exact same thing. And the way that people denote this formula is to say, look, we have 36 things and we are going to choose 9 of them. Right? And we don't care about order, so sometimes it'll be written as n choose k. Let me write it this way. So what did we do here? We have 36 things. We chose 9. So this numerator over here, this was 36 factorial. But 36 factorial would go all the way down to 27, 26, 25. It would just keep going. But we stopped only nine away from 36. So this is 36 factorial, so this part right here, that part right there, is not just 36 factorial. It's 36 factorial divided by 36, minus 9 factorial. What is 36 minus 9? It's 27. So 27 factorial-- so let's think about this-- 36 factorial, it'd be 36 times 35, you keep going all the way, times 28 times 27, going all the way down to 1. That is 36 factorial. Now what is 36 minus 9 factorial, that's 27 factorial. So if you divide by 27 factorial, 27 factorial is 27 times 26, all the way down to 1. Well, this and this are the exact same thing. This is 27 times 26, so that and that would cancel out. So if you do 36 divided by 36, minus 9 factorial, you just get the first, the largest nine terms of 36 factorial, which is exactly what we have over there. So that is that. And then we divided it by 9 factorial. And this right here is called 36 choose 9. And sometimes you'll see this formula written like this, n choose k. And they'll write the formula as equal to n factorial over n minus k factorial, and also in the denominator, k factorial. And this is a general formula that if you have n things, and you want to find out all of the possible ways you can pick k things from those n things, and you don't care about the order. All you care is about which k things you picked, you don't care about the order in which you picked those k things. So that's what we did here.