Combinatorics

Printable View

October 22nd 2008, 05:52 PM
Jeqle

Combinatorics

1) How many different four card hands can be dealt from a pack of 52 playing cards if at least one is an ace?

I thought there're 4 aces so it's just 4 * 51 * 50 * 49/4! but it's apparently 76145 .

2) Is there a fast way of finding all the four letter combinations of the word "mathematics"? So "math" is one, but "hatm" is the same one and while "mmat" is allowed "mmmt" isn't. I've managed to do this by case analysis (what happens when all letters are different and what happens when one letter repeats) and got 136 (which is right) but the method was long. Anyone know a fast way?
October 24th 2008, 07:42 AM
dely84

The 4 card hand with a fixed ace

Hi. You have misunderstood the combinatorial task needed here :)

1) So, you have 4-card hand out of 52 cards and want one of the cards to be an ace. All possible outcomes for 4-card hand out of 52 cards are
52C4 = 52*51*50*49/4! = 270 725.

If you think about all the possible combinations excluding any ace (all aces are 4, i.e. our deck decreases to 48) in the 4-card hand - they are 48C4 = 48*47*46*45/4! = 194 580. So, the answer you are looking for is:
{All possible combinations of 4-card hand out of 52} minus
{All possible combinations of 4-card hand out of 48} - we have "removed" all 4 aces i.e. 270 725 - 194 580 = 76 145 which is the answer you mentioned.

This valid as you may see for any denomination of a card deck - aces, jacks, 7s and etc...

2) Give me please, more clear and concise mathematical definition of the problem conditions(esp. def of a "word") - which letters to repeat or not any of them to be repeated, so that I will be able to help.. I think about permutations with repeat, if you know what I mean.
October 24th 2008, 09:23 AM
Jeqle

Hi

1) I can see why your method works (thank you very much for it), but what goes wrong with mine? What exactly have I worked out by doing 4 * 51 * 50 * 49/4! ?

2) A word is any 4 letters chosen from "mathematics".

You can use each letter in the word "mathematics" to form a new 4 letter word as many times as it repeats in the word "mathematics". So you can have 2 "m"s, 2 "a"s and 2 "t"s but only 1 "e", 1 "h", 1 "i", 1 "c" and 1 "s".
October 26th 2008, 07:06 PM
awkward

Quote:

Originally Posted by Jeqle

1) How many different four card hands can be dealt from a pack of 52 playing cards if at least one is an ace?

I thought there're 4 aces so it's just 4 * 51 * 50 * 49/4! but it's apparently 76145 .

2) Is there a fast way of finding all the four letter combinations of the word "mathematics"? So "math" is one, but "hatm" is the same one and while "mmat" is allowed "mmmt" isn't. I've managed to do this by case analysis (what happens when all letters are different and what happens when one letter repeats) and got 136 (which is right) but the method was long. Anyone know a fast way?

Hi Jeqle,

2) You want to count all the 4-letter combinations (the order of the letters is irrelevant) with letters taken from "mathematics". It's the 2 m's, 2 a's, and 2 t's that make this a little tricky. (By the way, it's somewhat misleading to call these "words"-- usually we consider the order of the letters relevant in a word.)

There are a couple of ways to do this. The straightforward, somewhat laborious way, is to break the combinations into cases based on how many multiple letters they contain and find the number of combinations in each case. So you have combinations like WXYZ (no duplicates), XXYZ and XXYY. Since there are only a few cases, this isn't all that hard. It would get a lot harder if, for example, you wanted to count all the 6-letter combinations taken from "mississippi".

I can't resist telling you, however, that if you study enough combinatorics you will encounter a beautiful idea called a "generating function" which reduces the computations to crank-turning-- in this case, just expanding a polynomial. The generating function for this problem is

$f(x) = (1+x)^5 (1 + x + x^2)^3$ .

The coefficient of $x^r$ when f is expanded is the number of r-letter combinations which can be built from "mathematics". You can expand f by hand (a little tedious, but straightforward), or you can use a computer algebra program if you have one, or if, as in this case, you are interested in only a single coefficient, then there are short-cut methods for the computation. One of the beauties of the generating function is that it contains the answer to many problems, not just the 4-letter combinations.

If you work it out you will find

$f(x) = x^{11} + 8 x^{10} + 31 x^9 + 77 x^8 + 136 x^7 + 179 x^6 + 179 x^5 + 136 x^4 + 77 x^3 + 31 x^2 + 8 x + 1$

So the number of 4-letter combinations is the 136, the coefficient of x^4, as claimed.

You can find material on generating functions in many books about combinatorics, including this on-line book:
http://www.math.dartmouth.edu/archiv...tes3-20-05.pdf
October 27th 2008, 12:48 AM
dely84

generating functions

Dear Awkward,

Could you please show the general formulae for this configuration generating function. Is there any solution of this problem with Permutations with repetition? Thanks in advance
October 27th 2008, 08:39 AM
Jeqle

Thanks a lot, Awkward, that helped.

Any thoughts on question 1 and why 4 * 51 * 50 * 49/4! doesn't work for question 1 and what it gives you if it's not the combinations of at least one ace?
October 27th 2008, 02:34 PM
awkward

Quote:

Originally Posted by dely84

Dear Awkward,

Could you please show the general formulae for this configuration generating function. Is there any solution of this problem with Permutations with repetition? Thanks in advance

Hi Dely84,

It's hard to state a general formula because there are so many different problems. But I'll break the generating function in this problem into its components for you. The $1 + x$ factor is there because of the 1-letter possibilities. Each letter can appear 0 (think $x^0 = 1$ ) or 1 times (think $x^1$ ). The exponent 5 in $(1+x )^5$ is there because there are 5 single letters ("heics"). The $1 + x + x^2$ factor is there for the 2-letter possibilities, each of which can appear 0 ( $x^0$ ), 1 ( $x^1$ ) or 2 ( $x^2$ ) times. The exponent 3 in $(1 + x + x^2)^3$ is there because there are 3 2-letter possibilities ("mat").

And as you guessed, there is a way to solve the equivalent problem with permutations (instead of combinations) with repetition. We need a different type of generating function for this, called an "exponential generating function". This time the function is

$g(x) = (1 + x)^3 (1 + x + (1/2!) x^2)^5$

This looks only a little different from the f(x) in the combinations problem, but the interpretation is very different. This time the coefficient of $x^r / r!$ when the polynomial is expanded is the number of r-letter permutations take from "mathematics". If we get the answer in a form without the r! divisor-- say $(409/4) x^4$ -- then we must multiply by r! to compensate: $(409/4) x^4 = 2454 x^4 / 4!$ . It turns out the coefficient $x^4 /4!$ in this problem is in fact 2454, so that is the number of 4-letter permutations with letters taken from "mathematics". The complete generating function when expanded is

$g(x) = 4989600 x^{11}/11! + 4989600 x^{10}/10! + 2630880 x^9/9! +$
$967680 x^8/8! + 277830 x^7/7! + 66150 x^6/6! + 13560 x^5/5! +$
$2454 x^4/4! + 399 x^3/3! + 59 x^2/2! + 8x + 1$

(Caveat: there is a good chance I have made a mistake somewhere in transcribing that monster.) This function provides the numbers of all the r-permutations taken from "mathematics" -- you just have to look at the right coefficient.

While I'm thinking about it, I should mention that there is a book by Niven, "Mathematics of Choice", with an introduction to generating functions at the high-school level. Many of the more advanced applications of generating functions require infinite series so you generally need some college math before studying them.
October 27th 2008, 03:37 PM
awkward

Quote:

Originally Posted by Jeqle

Thanks a lot, Awkward, that helped.

Any thoughts on question 1 and why 4 * 51 * 50 * 49/4! doesn't work for question 1 and what it gives you if it's not the combinations of at least one ace?

Hi Jegqle,

When you multiply 4 * 51 * 50 * 49 and then divide by 4!, you want 4 * 51 * 50 * 49 to count all the 4-card permutations with at least one ace, so each permutation is counted exactly 4! times-- then you compensate by dividing by 4!. But 4 * 51 * 50 * 49 counts only those permutations where an ace is in the first position, so not all 4! permutations are counted.
October 27th 2008, 04:02 PM
Jeqle

Oh yes I see now. Thank you very much.