Complicated Combinatorics Problem

• Apr 8th 2010, 11:50 AM
CogitoErgoCogitoSum
Complicated Combinatorics Problem
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.
• Apr 8th 2010, 02:48 PM
awkward
Quote:

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 $\displaystyle a_r$.

Let f be the exponential generating function of $\displaystyle a_r$, i.e.
$\displaystyle f(x) = \sum_{r=0}^{\infty} \frac{1}{r!} x^r$. Then
$\displaystyle 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 $\displaystyle a_6$, which is the coefficient of $\displaystyle \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

$\displaystyle a_6 = 728$,

as you predicted.