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\cdot2\cdot3 = 12.$

Ways to select {Red, Green, Blue} combination is $2\cdot 2\cdot 4 = 16.$

Ways to select {Red, Yellow, Blue} combination is $2\cdot3\cdot4 = 24.$

Ways to select {Green, Yellow, Blue} combination is $2\cdot3\cdot4 = 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\cdot2\cdot3\cdot4 = 48.$

$\endgroup$

1 Answer 1

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$
2
  • $\begingroup$ Thank you for answering! And great mathematical insight, especially the second approach involving the coefficients of x powers! :) $\endgroup$
    – xyzzy
    May 3, 2014 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, 2014 at 17:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .