In general I think I understand permutations fairly well. A simple example of permutations is drawing balls from an urn. I have 3 colors of balls, blue, green, and red, and I have 5 balls of each.

How many color patterns of balls can be drawn from the urn ? In this case the order of the color matters, but all balls of a single color are the same.

Answer: Simple, this is 3 * 3 * 3 * 3 * 3 = 243

Now Here Is The Real Question

What happens if I have fewer balls of each color than I will be drawing. What if I have 3 balls of each color, and want to draw 5 balls ?

Clearly the answer is fewer than 243, because some of the previous options are not available. But what is the equation? And more importantly, can it be generalized to a larger problem so if I had 30 balls of each color, and wanted to draw 50 balls total, I wouldn't have to do something like calculate the full set of permutations, and the subtract out the permutations where I have 31 of a color, and 32 of a color, etc

  • $\begingroup$ The "simple" answer is incorrect. There are by definition $15!$ ways to draw those $15$ balls from the urn. You seem to have counted the number of color patterns that can arise when you draw only $5$ balls from the urn (with or without replacement). When drawing $5$ balls without replacement, there are $15^{(5)}=15!/10!=15\cdot 14\cdot 13\cdot 12\cdot 11$ ways to draw them. $\endgroup$ – whuber Nov 4 '16 at 15:53
  • 1
    $\begingroup$ whuber: color patterns is what I am looking for here. That is what I intended to express with "in this case the order of the color matters, but all balls of a single color are the same" i'll try to edit the question to make it more clear $\endgroup$ – Fairly Nerdy Nov 4 '16 at 16:24
  • 1
    $\begingroup$ OK, thank you. Incidentally, the answer with 50 balls drawn without replacement from an urn of 30 balls of each color is 717830847380662283155566. It is about 99.9906% of $3^{50}$. $\endgroup$ – whuber Nov 4 '16 at 16:48
  • $\begingroup$ Aha! clearly you know the equation for this, because that number is too large to simulate. Can you explain ? $\endgroup$ – Fairly Nerdy Nov 4 '16 at 17:13
  • $\begingroup$ It's just brute force, I'm afraid. I computed the polynomial $$(x_1+x_2+x_3)^{50}$$ modulo the ideal generated by $\{x_1^{31}, x_2^{31}, x_3^{31}\}$ and then set all three variables to equal $1$. $\endgroup$ – whuber Nov 4 '16 at 17:15

Your Answer

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

Browse other questions tagged or ask your own question.