Quick combination and permutation questions

[Townsend]

I have a test coming up late next week or early in the week after next. In any case I want to be ready and so I have been practicing problems from the text a lot and just wanted to make sure I am not making any mistakes. If you see an answer that is wrong please let me know so I can try to see what I am doing wrong.

For this next problem there is a club consisting of six distinct men and seven distinct women.

1) In how many ways can we select a committee of four persons so that Mabel and Ralph do not serve together?

Since there are 13 people in the club there are C(12,4) possibilities for committees without Ralph and C(12,4) committees without Mabel. We want the union of the two sets. But we will end up counting the intersection twice and so we must subtract that off of our total. The intersection is where neither of the two are in the committee. That number is C(11,4). So we have 2*C(12,4)-C(11,4). Does that sound correct?

2) How many eight-bit strings contain exactly three 0's?

An eight-bit string with 3 0's has 5 1's. We can start by placing the first 0. There are 8 possibilities for that, then there are 7 possibilities for the next and 6 for the last one. So there are P(8,3) possible 8 bit strings with 3 zeros.

3) How many eight-bit strings contain three 0's in a row and five 1's?

Well since the 0's are all in a row we can place the first one and the other two will follow it. There are 6 places to start the first 0. So 6 is the answer

4) How many eight-bit strings contain at least two 0's in a row?

There is 1 eight bit string with 8 1's and no two zeros in a row. There are 8 eight-bit strings with 7 1's and 1 0 and no two zeros in a row. Now for an eight-bit string with 6 1's there are exactly 7 places to stick the 2 0's so that no two zeros are together. In other word the 0's must go between the 1's. So for 6 1's there are C(7,2) and then using the same technique there are C(6,3) strings with 5 1's and then there are C(5,4) strings with 4 1's. So we add up all these bad cases and subtract them from the total cases to get the number of good cases.

2^8-[1+8+C(7,2)+C(6,3)+C(5,4)]=201 strings that have at least 2 0's in a row.



For the next few questions I need to find the number of five card poker hands, selected from an ordinary 52-card deck, that have the properties indicated.

5) Containing four of a kind, that is, four cards of the same denomination.

Well there are 4 suits of any domination. So we just need to pick the domination which can be done in 4 ways. Then for the remaining card there are 52-4=48 possible choices. So by the multiplication principle we have 4*48.

6) Containing all spades.

There are 13 cards that are spades and so there is C(13,5) possible ways to have all spades.

7) Containing cards of exactly two suits.

Well first off we choose the two suits which can be done in 6 ways. Once this is done there are 26 cards left to pick from So there are C(26,5) ways to pick cards from two suits. But we must not count the ways that have all of either suit we take away C(13,5) two times, once for each possible suit. So in total 6*[C(26,5)-2*C(13,5)].

8) Consecutive and of the same suit.(assume the ace is the lowest denomination)

4 possible suits and 9 possible first cards so 4*9.

9) Consecutive (ace is lowest denomination).

Well there are 9 choices for the first card and there are 4 choices for the suit of that card. Then the next 4 cards we pick the suit for each from 4 possible suits. So in total we have 9*4^5.

10) Containing two of one denomination, two of another denomination, and one of a third denomination.


Well there are C(13,3) choices for the denomination. Then for two dominations that have two cards there are 6 choices for the two cards because there are 4 suits and we select 2. Then for the third denomination there are 4 choices. So in total there are C(13,3)*2*C(4,2)*4.

I think that is enough to today, maybe tomorrow I will post the rest of the questions.

Thanks for the help everyone.

 

[Hurkyl]

1) It often helps to try and do the problem in multiple different ways.
2) I count only 6 possibilities for the first zero...
3) I can't think of a cryptic response, so I'll just say it looks good.
4) Ditto
5) That's "denomination". Do you like the answer you get if you took the same approach for getting, say, 4 of a kind in 4 cards?
6) You sure?
7,8,9) Looks good.
10) Wrong.

 

[Townsend]

For number 2 the zeros do not have to be consecutive so I figure the first zero has 8 places it can go. Then since one spot is filled up there are 7 spaces for the second zero and like wise there are 6 spaces for the last zero. So I am sticking to my original answer on this one.


For number 6...they are all one suit so the question is asking how many combinations can come from 13 cards picked five at a time without regard to order. I don't see how there can be any other answer then the one I gave? But to answer your question, no I am not sure but I am hoping.

I will work on number 1 and 10.

Thanks Hurkyl.

 

[AKG]

1) In how many ways can we select a committee of four persons so that Mabel and Ralph do not serve together?

Since there are 13 people in the club there are C(12,4) possibilities for committees without Ralph and C(12,4) committees without Mabel. We want the union of the two sets. But we will end up counting the intersection twice and so we must subtract that off of our total. The intersection is where neither of the two are in the committee. That number is C(11,4). So we have 2*C(12,4)-C(11,4). Does that sound correct?

Yes.

An eight-bit string with 3 0's has 5 1's. We can start by placing the first 0. There are 8 possibilities for that, then there are 7 possibilities for the next and 6 for the last one. So there are P(8,3) possible 8 bit strings with 3 zeros.

So, we can place the first 0 at position 7, then the next at one of the remaining 7 positions, say position 3, then the last at 2. Alternatively, your count allows us to place the first at position 3, the second at 2, and the last at 7. What you're really doing is choosing 3 of the 8 positions to contain 0's. It doesn't matter if you choose positions 3, 7, and 8 to hold zeroes, or positions 7, 3, and 8, i.e. order doesn't matter. You're just choosing, not permuting, so the answer is C(8, 3).

3) How many eight-bit strings contain three 0's in a row and five 1's?

Well since the 0's are all in a row we can place the first one and the other two will follow it. There are 6 places to start the first 0. So 6 is the answer

Right.

4) How many eight-bit strings contain at least two 0's in a row?

There is 1 eight bit string with 8 1's and no two zeros in a row. There are 8 eight-bit strings with 7 1's and 1 0 and no two zeros in a row. Now for an eight-bit string with 6 1's there are exactly 7 places to stick the 2 0's so that no two zeros are together.

There are more than that.

In other word the 0's must go between the 1's.

You mean the 1's must go between the 0's?

So for 6 1's there are C(7,2)

There are C(8,2) ways to place 2 0's (and 6 1's), and 7 of those combinations will have adjacent 0's, so you'd have C(8,2) - 7. This is C(7,2), so you're right, but I don't see how you got this number.

and then using the same technique there are C(6,3) strings with 5 1's and then there are C(5,4) strings with 4 1's. So we add up all these bad cases and subtract them from the total cases to get the number of good cases.

2^8-[1+8+C(7,2)+C(6,3)+C(5,4)]=201 strings that have at least 2 0's in a row.

If you have 5 or more 0's, some must be adjacent (as you know). If you have 4 zeroes, there are only 2 strings with no adjacent 0's, "01010101" and "10101010". C(5,4) is 5, on the other hand.

Now if you have 3 zeroes, consider the case where we have zeroes on the ends, i.e. "01xxxx10". 4 of these situations have no adjacent zeroes.

If there is a zero on one end but not the other, i.e. "01xxxxx1", then after the first 0, we have "1xxxxx1". This reduces to the problem of finding a way to place 2 0's and 3 1's such that the 0's aren't adjacent. There are C(5,2) total ways to place the numbers, and clearly 4 ways that will lead to adjacent 0's, so for the case "01xxxxx1", the answer is C(5,2) - 4. By symmetry, if the zero were on the far right, we would have another C(5,2) - 4.

Now, the only case is the one where we have "1xxxxxx1". How do we place 3 0's with 3 1's to have no two adjacent 0's? Between the end 1's, we have "xxxxxx". Similar to the case of 4 0's (and 8 total spots, or 4 1's), we have only two options, "010101" or "101010".

In total, for 3 0's, there are 4 + 2 + 2(C(5,2) - 4) = 6 + 2(6) = 18 ways to have no adjacent zeroes

If we have 2 0's, we found that there were C(7,2) ways to have no adjacent zeroes.

If we have 1 zero, then there are 8 ways, as you know, and 1 way if there are no zeroes. In total, we should have:

2^8 - 1 - 8 - C(7,2) - 18 - 2 = 2^8 - 29 - 21 = 206. You and I got slightly different numbers.

5) Containing four of a kind, that is, four cards of the same denomination.

Well there are 4 suits of any domination. So we just need to pick the domination which can be done in 4 ways. Then for the remaining card there are 52-4=48 possible choices. So by the multiplication principle we have 4*48.

This should be 13*48. There are 13 denominations (so 13 different 4-of-a-kinds) and 48 possibilites for the extra card.

6) Containing all spades.

There are 13 cards that are spades and so there is C(13,5) possible ways to have all spades.

Yes.

7) Containing cards of exactly two suits.

Well first off we choose the two suits which can be done in 6 ways. Once this is done there are 26 cards left to pick from So there are C(26,5) ways to pick cards from two suits. But we must not count the ways that have all of either suit we take away C(13,5) two times, once for each possible suit. So in total 6*[C(26,5)-2*C(13,5)].

Yes.

8) Consecutive and of the same suit.(assume the ace is the lowest denomination)

4 possible suits and 9 possible first cards so 4*9.

Yes.

9) Consecutive (ace is lowest denomination).

Well there are 9 choices for the first card and there are 4 choices for the suit of that card. Then the next 4 cards we pick the suit for each from 4 possible suits. So in total we have 9*4^5.

Yes.

10) Containing two of one denomination, two of another denomination, and one of a third denomination.


Well there are C(13,3) choices for the denomination. Then for two dominations that have two cards there are 6 choices for the two cards because there are 4 suits and we select 2. Then for the third denomination there are 4 choices. So in total there are C(13,3)*2*C(4,2)*4.

Let's say the denominations we get are 3, 8, J. You do not account for the fact that it might be the 3 of which we only have 1, or the Jack, or the 8. You need to multiply your answer by 3. C(13,3) to choose the 3 denominations. C(3,1) to choose the 1 denomination of those 3 that we'll only have 1 of. Then C(4,1) for that denomination that we have only one of, and twice C(4,2) becase we have two for which we choose 2 cards.

 

[Townsend]

So, we can place the first 0 at position 7, then the next at one of the remaining 7 positions, say position 3, then the last at 2. Alternatively, your count allows us to place the first at position 3, the second at 2, and the last at 7. What you're really doing is choosing 3 of the 8 positions to contain 0's. It doesn't matter if you choose positions 3, 7, and 8 to hold zeroes, or positions 7, 3, and 8, i.e. order doesn't matter. You're just choosing, not permuting, so the answer is C(8, 3).

Yes you are so right, now if I ever get asked this on my test I will not make this same mistake. Thanks

For problem 4 I think I am right.

You mean the 1's must go between the 0's?

No, I mean that since we want to know how many strings with 6 1's have no two zeros together. So there are 7 spaces between 6 1's in which the 2 zeros can go.
_1_1_1_1_1_1_

So we have 7 places to pick from and we pick 2 at a time. so we get C(7,2).

Now for 5 1's there are 6 spaces between the ones where the 0's can go.

_1_1_1_1_1_

So we have C(6,3), then for 4 1's there are C(5,4) and for less than 4 1's the string must have at least 2 zeros in a row.

So we have 2^8 total strings and we have [1+8+C(7,2)+C(6,3)+C(5,4)] strings that have no two zeros in a row. That works out to 201 strings. I check it about 5 times now so I don't think I made an arithmetic error.

For number 5 I finally see what I did wrong, I guess I just missed your hint Hurkyl but I got it now.


I still need to figure #10 out...I will get back to that.

Thanks again..

 

[learningphysics]

If you have 4 zeroes, there are only 2 strings with no adjacent 0's, "01010101" and "10101010". C(5,4) is 5, on the other hand.

10101010
01101010
01011010
01010110
01010101

Exactly five.

 

[AKG]

Yup, you're right about 4. learningphysics pointed out the three cases I was missing for 4 zeroes. Also, if there are 3 zeroes, when I said:

Now, the only case is the one where we have "1xxxxxx1". How do we place 3 0's with 3 1's to have no two adjacent 0's? Between the end 1's, we have "xxxxxx". Similar to the case of 4 0's (and 8 total spots, or 4 1's), we have only two options, "010101" or "101010".

I was missing the cases "010110" and "011010". The type of cases I neglected to consider were the same. Those 2 plus the 3 learningphysics pointed out account for the discrepancy of 5 between our results.