1
$\begingroup$

Given a set of colored balls (multiple balls having the same color is allowed), is there any direct combinatorial approach to determine the total number of ways to select n distinctly-colored balls? Note: n will be less than or equal to the total number of distinct colors.

Example:- Let's say we have 11 colored balls. 2 are Red, 2 are Green, 3 are Yellow, and 4 are Blue. Here, there are 4 distinct colors. So n will be less then or equal to 4.

Consider n = 3. The possible combinations of selecting 3 distinctly-colored balls are {Red, Green, Yellow}, {Red, Green, Blue}, {Red, Yellow, Blue}, {Green, Yellow, Blue}.

Ways to select {Red, Green, Yellow} combination is 2*2*3 = 12. Ways to select {Red, Green, Blue} combination is 2*2*4 = 16. Ways to select {Red, Yellow, Blue} combination is 2*3*4 = 24. Ways to select {Green, Yellow, Blue} combination is 2*3*4 = 24.

Hence the total number of ways to select 3 distinctly-colored balls = 12+16+24+24 = 76.

Another example is when n = 2, the answer will be 4 Red-Green combinations, 6 Red-Yellow combinations, 8 Red-Blue combinations, 6 Green-Yellow combinations, 8 Green-Blue combinations, 12 Yellow-Blue combinations. Total = 4+6+8+6+8+12 = 44.

Last example when n = 4, the answer is 2*2*3*4 = 48.

$\endgroup$
1
$\begingroup$

I doubt there is a nice combinatorial solution.

Suppose the $i$th colour has $b_i$ distinguishable balls and there are $t$ different colours.

Essentially I see three possible approaches: one is the approach you took of finding the possible patterns of colours, multiplying the numbers, and then summing over the patterns.

The second is to consider the coefficient of $x^n$ in the expansion of $$(1+b_1x)(1+b_2x)\cdots(1+b_ix)\cdots.$$

The third is with the recurrence $f(i,c)=f(i,c-1)+b_if(i-1,c-1)$ when $i \le c$ and $f(i,c)=0$ when $i \gt c$, starting with $f(0,c)=1$. You want $f(n,t)$.

$\endgroup$
  • $\begingroup$ Thank you for answering! And great mathematical insight, especially the second approach involving the coefficients of x powers! :) $\endgroup$ – xyzzy May 3 '14 at 18:08
  • $\begingroup$ Hi again Henry. A related doubt... Is there any way to deduce the number of occurrences of each color in all subsets extractable for a particular n value? Equation format for the above example: 1 + 11x + 44x^2 + 76x^3 + 48x^4. Considering n = 3, the number of subsets with exactly 3-distinct colors is 76. Can we somehow arrive at occurrences of Red in all these subsets is 52 (12+16+24); occurrences of Green in all these subsets is 52 (12+16+24); occurrences of Yellow in all these subsets is 60 (12+24+24); occurrences of Blue in all these subsets is 64 (16+24+24). $\endgroup$ – xyzzy May 5 '14 at 17:22

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.