Suppose there is a jar with $7$ balls: $4$ red, $2$ green and $1$ blue.
In how many unique ways can we choose $3$ balls?

Just by considering all the possibilities, I found out the answer is $6$. Namely:

  • red, red, red
  • red, red, green
  • red, red, blue
  • green, green, red
  • green, green, blue
  • blue, green, red

I was wondering if it is possible to express the solution in terms of the amount of different colors (in this case $3$) and the quantity per color. (in this case $4$, $2$ and $1$)

  • $\begingroup$ It is possible. That said, for the given numbers, simply listing the possibilities is probably the most efficient method. $\endgroup$ Nov 16 '18 at 18:20
  • $\begingroup$ Another way to look at it is : Let $x_1,x_2,x_3$ be the number of red, green and blue balls respectively. You wish to find all possible solutions to $x_1+x_2+x_3=3$ such that $0\leq x_1\leq 4, 0\leq x_2\leq 2, 0\leq x_3\leq 1$. By the way your answer is $^7C_3$ I guess. $\endgroup$ Nov 16 '18 at 18:22
  • $\begingroup$ One might also think of this as a sample problem for counting the number of contingency tables with two rows and three columns having prescribed marginal sums. Even for two rows but arbitrarily many columns such counting problems have been shown to be NP hard. $\endgroup$
    – hardmath
    Nov 16 '18 at 18:25
  • $\begingroup$ @YadatiKiran $\binom{7}{3}$ is an answer to a related but different question where the balls were all distinctly labeled. Here, presumably, the red balls are all identical, etc... Your rephrasing of the question however is correct, but the method of solution would likely either involve brute force, or inclusion-exclusion with stars and bars which is likely just as tedious as brute force here. $\endgroup$
    – JMoravitz
    Nov 16 '18 at 18:35
  • $\begingroup$ An alternate solution, which if you have access to computer software is easy to implement for reasonable numbers (but is practically brute force in disguise) is to look at the coefficient of $x^3$ in the expansion of $(1+x+x^2+x^3+x^4)(1+x+x^2)(1+x)$. $\endgroup$
    – JMoravitz
    Nov 16 '18 at 18:37

Consider the polynomial $$\eqalign{p(x)&:=(1+x+x^2+x^3+x^4)(1+x+x^2)(1+x)\cr &=(1-x^5)(1-x^3)(1-x^2)(1-x)^{-3}\cr &=(1-x^5)(1-x^3)(1-x^2)\sum_{k\geq0}{2+k\choose k}x^k\ .\cr}\tag{1}$$ For each admissible choice of $r\in[0 .. 4]$ red balls, $g\in[0 .. 2]$ green balls, and $b\in[0 .. 1]$ blue balls the expansion of this polynomial creates a term $x^r\,x^g\,x^b=x^{r+g+b}$. Now we want $r+g+b=3$. It follows that we have to extract $N:={\rm coeff}[x^3]$ on the last line of $(1)$. Since $$(1-x^5)(1-x^3)(1-x^2)=1-x^2-x^3+{\rm higher\ terms}$$ it follows that $$N={2+3\choose3}-{2+1\choose1}-{2+0\choose0}=6\ .$$


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.