Complicated Combinatorics Problem

**CogitoErgoCogitoSum** · April 8th 2010, 11:50 AM

In how many ways can a we arrange, in a row, six balls... when we have to choose from seven non-unique cricket balls, six non-unique tennis balls and five non-unique squash balls?

In total, 18 balls from three unique sets, each set of which contains non-unique entities, and each set is differently sized and one of which contains one fewer ball than we wish to arrange.

The answer is supposed to be 728, according to my reference. Im just not sure how to solve it. I could probably solve this by breaking it down into specific cases, and adding it all up... but Id might as well list each possible combination if Im going to do that. Im looking for a simpler method.

**awkward** · April 8th 2010, 02:48 PM

Originally Posted by CogitoErgoCogitoSum

In how many ways can a we arrange, in a row, six balls... when we have to choose from seven non-unique cricket balls, six non-unique tennis balls and five non-unique squash balls?

In total, 18 balls from three unique sets, each set of which contains non-unique entities, and each set is differently sized and one of which contains one fewer ball than we wish to arrange.

The answer is supposed to be 728, according to my reference. Im just not sure how to solve it. I could probably solve this by breaking it down into specific cases, and adding it all up... but Id might as well list each possible combination if Im going to do that. Im looking for a simpler method.

Hi Cogito,

You may or may not like the following solution, which uses exponential generating functions.

Let's say, more generally, we want to find the number of ways to select r balls from the set of cricket, tennis, and squash balls. Call this number $a_r$ .

Let f be the exponential generating function of $a_r$ , i.e.
$f(x) = \sum_{r=0}^{\infty} \frac{1}{r!} x^r$ . Then
$f(x) = (1 + x + \frac{1}{2!}x^2 + \dots + \frac{1}{7!}x^7) \cdot (1 + x + \frac{1}{2!}x^2 + \dots + \frac{1}{6!}x^6) \cdot (1 + x + \frac{1}{2!}x^2 + \dots + \frac{1}{5!}x^5)$
by elementary properties of exponential generating functions. (It's easy to see once you know how.) The answer to your problem is $a_6$ , which is the coefficient of $\frac{1}{6!} x^6$ when f is expanded.

The bad news is that finding the coefficient by pencil and paper essentially boils down to listing the cases, which you said you want to avoid. But the good news is that there are many computer algebra systems (Wolfram Alpha, for one) which will expand f for you. When this is done we find

$a_6 = 728$ ,

as you predicted.

Thread: Complicated Combinatorics Problem

LinkBack

Thread Tools

Display

Complicated Combinatorics Problem

Similar Math Help Forum Discussions

A complicated problem

Please help - complicated D=RT problem

Complicated Log problem

complicated problem...

Complicated Problem!!

Search Tags