1
$\begingroup$

So, I'm working out one of my assignments and I'm a little bit stuck on this problem:

A fish store is having a sale on guppies, tiger barbs, neons, swordtails, angelfish, and siamese fighting fish (6 kinds). How many ways are there to choose 24 fish with at least 1 guppy, at least 2 tiger barbs, at least 3 neons, exactly 1 swordtail, at least two angelfish, and no more than 3 siamese fighting fish?

I feel like the way to approach this problem is to use r-combinations with repetition (because the fish store isn't running out of any of the fish) and subtract the combinations that I don't want. Here's what I've got so far:

We need at least 1 guppy, 2 tiger barbs, 3 neons, and 2 angelfish. If we set those aside (all 8 of those), we're down to $24-8$, or 16 remaining fish to choose. Add the 1 swordtail, and we only need to choose $24-9$ or 15 fish out of 5 ($(6-1)$ because there were 6 kinds, but we can only have 1 of the swordtail).

All this accounted for, utilizing r-combination with repetition, $\binom{n+r-1}{r}$: $$\binom{15+5-1}{15}=3,876$$

BUT I can't have more than 3 siamese fighting fish! How do I subtract all the groups with more than 3 siamese fighting fish?

Any help would be much appreciated! Also, if I've made any other errors, please point those out and I'll edit the question appropriately. We covered it in class, but it went so quick I didn't get it down in my notes. Thanks!

$\endgroup$
1
$\begingroup$

It seems like you could just sum up all the cases where you have $0$, $1$, $2$, and $3$ siamese fighting fish separately. If there are no siamese fighting fish, then we can choose $15$ out of $4$ types, if there is exactly one siamese fighting fish, then we can choose $14$ fish out of $4$ types, if there are exactly two, then we can choose $13$ fish out of $4$ types, and if there are exactly three then we can choose $12$ fish out of $4$ types. This would give

${15+4-1 \choose 15}+{14+4-1 \choose 14}+{13+4-1 \choose 13}+{12+4-1 \choose 12}$

$\endgroup$
2
  • $\begingroup$ Hi there, thanks for the quick answer! I guess I could do it that way, but what about when the "at most" number is much bigger? Is there a simpler way? $\endgroup$ – definitelyokay Dec 2 '15 at 0:18
  • $\begingroup$ Off the top of my head, I am not sure, sorry. $\endgroup$ – mathochist Dec 2 '15 at 0:53
0
$\begingroup$

Here is an approach using generating functions. The generating function for the guppies is $g+g^2+g^3+\cdots ={g\over 1-g}$. In the same way, the generating functions for the other 5 types of fish are ${t^2\over 1-t}$ (tiger barbs), ${n^3\over 1-n}$ (neons), $sw$ (swordtails), ${a^2\over 1-a}$ (angelfish), and $1+s+s^2+s^3$ (siamese fighting fish). The generating function in six variables is $$\Phi(g,t,n,sw,a,s)={g\, t^2\, n^3\, sw\, a^2\, (1+s+s^2+s^3)\over (1-g)(1-t)(1-n)(1-a)},$$ whose coefficients give the counts for all acceptable purchases of fish.

Since we only care that the total number of fish is 24, and not the particular makeup of types, we may look at a simpler generating function where all six variables are replaced by the variable "$f$": \begin{eqnarray*}G(f)&=&\Phi(f,f,f,f,f,f)\\[5pt] &=&{f^9(1+f+f^2+f^3)\over (1-f)^4}\\[5pt] &=&\sum_{j\geq 0}{j+3\choose 3} (f^{9+j}+f^{10+j}+f^{11+j}+f^{12+j}). \end{eqnarray*}

Extracting the coefficient of $f^{24}$ in $G(f)$ gives ${18\choose 3}+{17\choose 3}+{16\choose 3}+{15\choose 3}=2511.$

This isn't as easy as mathochist's solution, but you can use the same idea for more complicated problems.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer! I appreciate that you took the time to solve it, especially in such an elegant fashion. Unfortunately, I don't know enough math to follow. I'm sure it's great for larger counting problems. $\endgroup$ – definitelyokay Dec 2 '15 at 1:32
  • $\begingroup$ Glad to help. Generating functions are incredibly useful! Come back to this solution when you are ready. $\endgroup$ – user940 Dec 2 '15 at 1:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.