2
$\begingroup$

A bag contains colored balls:

  • 8 red balls
  • 4 white balls
  • 4 blue balls
  • 4 green balls
  • 2 purple balls
  • 2 orange balls
  • 1 yellow ball
  • 1 black ball

Total of 26 balls.

I'd like to determine the number of combinations of balls when 8 are chosen. Doing a combination like 26C8 obviously disregards the order of the chosen balls, but I'd like to also disregard sets that identical colors (example, there are 8 ways (9c8) to have 7 red balls and one 1 black ball, because there are 8 different red balls, but I really want to count this as one combination).

I figure it probably ends up being 26C8 divided by....something? Any ideas?

$\endgroup$
1
  • $\begingroup$ Sadly it does not "end up being 26C8 divided by... something". You are counting how many color combinations are possible (outcomes distinguishable only by the number of each color). While the possible colors will add up to $8$ in each outcome, and the colors give an "order" to those summands, it is not as simple as how many weak compositions of $8$ there are with at most $8$ summands (the number of colors), because you have bounds on how large certain summands can be (only the count of red balls can be as large as all $8$). $\endgroup$
    – hardmath
    Jun 15 '16 at 0:14
1
$\begingroup$

I am not sure there's a simple way of dividing it out. Here's a simplified example to show why:

Suppose you have 1 red, 2 green, and 4 blue balls (total = 7). You want to pick 3 of them.

If all of the balls were distinguishable, there would be 7C3 = 35 choices.

As for the case where same-colored balls are indistinguishable, the problem is simple enough that we can exhaustively list all of the solutions:

$$RGG, RBG, RBB, GGB, GBB, BBB.$$

There are six possibilities, and six is not a factor of 35. So in general for picking some number of balls from a collection, there is probably not a simple way to start from the case where all balls are distinguishable and divide by something to get the case where some balls are indistinguishable.

Edit: I believe the answer to your original question is that there are 1941 ways of picking 8 things from that group. I wrote a short Python script to crunch the numbers:

balls = [8,4,4,4,2,2,1,1] # original example
# balls = [1,2,4] # simplified example

def combos(pick, bag) :
    # pick: how many total items to pick
    # bag: a list of how many of each color you have.

    if pick == 0 :
        return 1
    if bag == [] :
        return 0

    # consider the next color in the bag
    this_color_count = bag[0]
    rest = bag[1:]

    # decide how many of this color to use. (k)
    return sum([combos(pick-k, rest) 
                for k in range(0, min(pick, this_color_count)+1)])

print combos(8, balls)
$\endgroup$
0
$\begingroup$

Let \begin{align*} x_1 & = \text{number of red balls selected}\\ x_2 & = \text{number of white balls selected}\\ x_3 & = \text{number of blue balls selected}\\ x_4 & = \text{number of green balls selected}\\ x_5 & = \text{number of purple balls selected}\\ x_6 & = \text{number of orange balls selected}\\ x_7 & = \text{number of yellow balls selected}\\ x_8 & = \text{number of black balls selected} \end{align*} The number of ways of selecting eight of the twenty-six balls is the number of solutions of the equation $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 = 8 \tag{1}$$ in the non-negative integers subject to the restrictions $x_2, x_3, x_4 \leq 4$, $x_5, x_6 \leq 2$, and $x_7, x_8 \leq 1$.

If there were no restrictions, a particular solution would correspond to the placement of seven addition signs in a row of eight ones. For instance, $$1 1 + 1 + 1 + + 1 1 + 1 + + 1$$ corresponds to the solution $x_1 = 2$, $x_2 = 1$, $x_3 = 1$, $x_4 = 0$, $x_5 = 2$, $x_6 = 1$, $x_7 = 0$, and $x_8 = 1$. Hence, the number of solutions of equation 8 in the non-negative integers is $$\binom{8 + 7}{7} = \binom{15}{7}$$ since we must select which seven of the fifteen symbols (eight ones and seven addition signs) will be addition signs.

From these, we must exclude those solutions that violate one or more of the restrictions.

Suppose the restriction $x_2 \leq 4$ is violated. Then $y_2 = x_2 - 5$ is a non-negative integer. Substituting $y_2 + 5$ for $x_2$ in equation 1 yields \begin{align*} x_1 + y_2 + 5 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 & = 8\\ x_1 + y_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 & = 3 \tag{2} \end{align*} Equation 2 is an equation in the non-negative integers with $$\binom{3 + 7}{7} = \binom{10}{7}$$ solutions. By symmetry, there are also $\binom{10}{7}$ solutions in which the restriction $x_3 \leq 4$ is violated and $\binom{10}{7}$ in which the restriction $x_4 \leq 4$ is violated.

Suppose the restriction $x_5 \leq 2$ is violated. Then $y_5 = x_5 - 3$ is a non-negative integer. Substituting $y_5 + 3$ for $x_5$ in equation 1 yields \begin{align*} x_1 + x_2 + x_3 + x_4 + y_5 + 3 + x_6 + x_7 + x_8 & = 8\\ x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 & = 5 \tag{3} \end{align*} Equation 3 is an equation in the non-negative integers with $$\binom{5 + 7}{7} = \binom{12}{7}$$ solutions. By symmetry, there are also $\binom{12}{7}$ solutions in which the restriction $x_6 \leq 2$ is violated.

Suppose the restriction $x_7 \leq 1$ is violated. Then $y_7 = x_7 - 2$ is a non-negative integer. Substituting $y_7 + 2$ for $x_7$ in equation 1 yields \begin{align*} x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + y_7 + 2 + x_8 & = 8\\ x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 & = 6 \tag{4} \end{align*} Equation 4 is a non-negative integer with $$\binom{6 + 7}{7} = \binom{13}{7}$$ solutions. By symmetry, there are also $\binom{13}{7}$ solutions in which the restriction $x_8 \leq 1$ is violated.

It is also possible for two or more of the restrictions to be violated simultaneously.

Suppose the restrictions $x_2 \leq 4$ and $x_5 \leq 2$ are both violated. Then, if we define $y_2$ and $y_5$ as above, we obtain \begin{align*} x_1 + y_2 + 5 + x_3 + x_4 + y_5 + 3 + x_6 + x_7 + x_8 & = 8\\ x_1 + y_2 + x_3 + x_4 + y_5 + x_6 + x_7 + x_8 & = 0 \tag{5} \end{align*} Equation 5 is an equation in the non-negative integers with one solution. By symmetry, there is also one solution for simultaneous violations of the restrictions on each of the following pairs of variables: $x_2$ and $x_6$, $x_3$ and $x_5$, $x_3$ and $x_6$, $x_4$ and $x_5$, and $x_5$ and $x_6$.

Suppose the restrictions $x_2 \leq 4$ and $x_7 \leq 1$ are both violated. Then if $y_2$ and $y_7$ are defined as above, we obtain \begin{align*} x_1 + y_2 + 5 + x_3 + x_4 + x_5 + x_6 + y_7 + 2 + x_8 & = 8\\ x_1 + y_2 + x_3 + x_4 + x_5 + x_6 + y_7 + x_8 & = 1 \tag{6} \end{align*} Equation 6 is an equation in the non-negative integers with eight solutions. By symmetry, there are also eight solutions for simultaneous violations of each of the following pairs of variables: $x_2$ and $x_8$, $x_3$ and $x_7$, $x_3$ and $x_8$, $x_4$ and $x_7$, and $x_7$ and $x_8$.

Suppose the restrictions $x_5 \leq 2$ and $x_6 \leq 2$ are both violated. Let $y_5$ be defined as above; let $y_6 = x_6 - 3$. Then $y_6$ is a non-negative integer. Substituting $y_5 + 3$ for $x_5$ and $y_6 + 3$ for $x_6$ in equation 1 yields \begin{align*} x_1 + x_2 + x_3 + x_4 + y_5 + 3 + y_6 + 3 + x_7 + x_8 & = 8\\ x_1 + x_2 + x_3 + x_4 + y_5 + y_6 + x_7 + x_8 & = 2 \tag{7} \end{align*} Equation 7 is an equation in the non-negative integers with $$\binom{2 + 7}{7} = \binom{9}{7}$$ solutions.

Suppose the restrictions $x_5 \leq 2$ and $x_7 \leq 1$ are both violated. Let $y_5$ and $y_7$ be defined as above. Then \begin{align*} x_1 + x_2 + x_3 + x_4 + y_5 + 3 + x_6 + y_7 + 2 + x_8 & = 8\\ x_1 + x_2 + x_3 + x_4 + y_5 + x_6 + y_7 + x_8 & = 3 \tag{8} \end{align*} Equation 8 is an equation in the non-negative integers with $$\binom{3 + 7}{7} = \binom{10}{7}$$ solutions. By symmetry, there are also $\binom{10}{7}$ solutions in which there are simultaneous violations of the restrictions on the following pairs of variables: $x_5$ and $x_8$, $x_6$ and $x_7$, and $x_6$ and $x_8$.

Suppose the restrictions $x_7 \leq 1$ and $x_8 \leq 1$ are both violated. Let $y_7$ be as above; let $y_8 = x_8 - 2$. Then $y_8$ is a non-negative integer. Substituting $y_7 + 2$ for $x_7$ and $y_8 + 2$ for $x_8$ yields \begin{align*} x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + y_7 + 2 + y_8 + 2 & = 8\\ x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + y_7 + y_8 & = 4 \tag{9} \end{align*} Equation 9 is an equation in the non-negative integers with $$\binom{4 + 7}{7} = \binom{11}{7}$$ solutions.

Suppose the restrictions $x_5 \leq 2$, $x_6 \leq 2$, and $x_7 \leq 1$ are each violated. Let $y_5$, $y_6$, and $y_7$ be as above. Then \begin{align*} x_1 + x_2 + 5 + x_3 + x_4 + y_5 + 3 + y_6 + 3 + y_7 + 2 + x_8 & = 8\\ x_1 + x_2 + x_3 + x_4 + y_5 + y_6 + y_7 + x_8 & = 0 \tag{10} \end{align*} Equation 10 is an equation with one solution in the non-negative integers. By symmetry, there is also one solution in which the restrictions on $x_5$, $x_6$, and $x_8$ are each violated.

Suppose the restrictions $x_5 \leq 2$, $x_7 \leq 1$, and $x_8 \leq 1$ are each violated. Let $y_5$, $y_7$, and $y_8$ be as above. Then \begin{align*} x_1 + y_2 + 5 + x_3 + x_4 + y_5 + 3 + x_6 + y_7 + 2 + y_8 + 2 & = 8\\ x_1 + y_2 + x_3 + x_4 + y_5 + x_6 + y_7 + y_8 & = 1 \tag{11} \end{align*} Equation 11 is an equation in the non-negative integers with eight solutions. By symmetry, there are also eight solutions in which the restrictions on $x_6$, $x_7$, and $x_8$ are each violated.

By the Inclusion-Exclusion Principle, the number of distinguishable ways eight balls can be selected from the given collection of twenty-six balls is $$\binom{15}{7} - 3\binom{10}{7} - 2\binom{12}{7} - 2\binom{13}{7} + 6\binom{7}{7} + 6\binom{8}{7} + \binom{9}{7} + 4\binom{10}{7} + \binom{11}{7} - 2\binom{7}{7} - 2\binom{8}{7} = 1941$$

$\endgroup$
0
$\begingroup$

Let's generalize the problem a little and ask for the number of combinations when $r$ balls are chosen; let this number be $a_r$. Define the generating function $$f(x) = \sum_{r=0}^{\infty} a_r x^r$$ It's "obvious" (with some study) that $$f(x) = (1+x)^2 (1+x+x^2)^2 (1+x+x^2+x^4)^3 (1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8)$$ Expanding $f(x)$ in a computer algebra system shows that the coefficient of $x^8$, i.e. $a_8$, is $1941$; this is the answer to the original problem.

One on-line reference for generating functions is Bogart's "Enumerative Combinatorics Through Guided Discovery", Chapter 4. http://www.math.dartmouth.edu/archive/kpbogart/public_html/ComboNotes3-20-05.pdf

$\endgroup$

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.