Blogs, Mathematical Reasoning, MR Study Help

Counting Balls

My introduction to proofs class will be having an exam later this week. In order to help them prepare, I will be posting solutions to their practice exam throughout the next few posts. Here, we will review some combinatorics and look at the different ways that we can pull balls out of a bag. You can find more information on counting in the post Counting, Permutations and Combinations

You have 30 distinct balls placed in a bag.

For both of the scenarios we will be looking at, we will be assuming that we have placed 30 distinct balls inside of a bag. We want to pull some of these balls out as part of a game. As we do so, we hope to determine the total number of different ways that we can do this.

You reach in pull out a ball and write down which one you get. You then put the ball back in and repeat until you have pulled out a total of 7 balls.

Photo by Jopwell x PGA on Pexels.com

In this situation, we will pull balls out the bag one at, noting the result each time. Since we are writing the results down as we pull the balls out, we are also noting in which order the balls are pulled. In order to determine the number of distinct ways we can do this, we need to determine what would constitute a distinct option. Two options will be distinct if the ball pulled at any of the seven times is different. That is two options will be the same if

  • The balls pulled on the first pulls correspond.
  • The balls pulled on the second pulls correspond.
  • The balls pulled on the “nth” pulls correspond for n between 1 and 7.

Keeping this in mind, we will count the possibilities as we construct a pull. That is, we imagine doing the process and outline what we do. We would need to pull a first ball, then a second, then a third and so on through the seventh ball. In each of these cases, there will be thirty options for which ball to pull, because we put the balls back into the bag.

A different at any point leads to a different option, so we can find the total number of options by multiplying the options for each step together. We then get that there are \(30*30*30*30*30*30*30=30^{7} \approx 21.9\) billion ways to pull a ball out the bag seven times if we replace the ball each time.

We note that in this situation we had that we repeated something multiple times. Over the course of these repetitions, the order in which a result occurred did matter. Also, the same result was allowed for different pulls. In general, if we run a repeated process k times with n options each time where order matters and repetition is allowed, we will have \(n^{k}\) total distinct outcomes.

You reach in pull out a ball and write down which one you get and place the ball to the side. You then repeat until you have pulled out a total of 7 balls.

Photo by Jopwell x PGA on Pexels.com

This situation is similar to the last in that we will have to pull a ball out of the bag seven times. Each time we do so, we write down the result. As we do so, we will be keeping track of the order in which we pulled the balls out. The difference in this situation is that we will not put the ball back in once we have pulled it out.

As we did last time, we want to think about what would constitute different results. Again case, we will get different results if any of the pulls are distinct. We can follow the process we used last time in order to construct the possible results. The difference here is that each time we pull out a ball, we won’t replace it. This will result in have one less possible outcome for each new pull of a ball.

We will therefore find that the first pull will have 30 options, the second 29, the third 28 and so on. The total number of distinct outcomes will then be \(30*29*28*27*26*25*24=\frac{30!}{23!} \approx 10.2\) billion ways to pull a ball out one at a time without replacing the balls.

In this case, we again repeated the same process multiple times. While doing so, the order the results occurred in again mattered; however, we were not allowed to have the same result multiple times. In general, if we do a repeated process k times with n total possible results for the first outcome where the order of the results matter and we are not able to repeat results, we will have a total of \(\frac{n!}{(n-k)}!\) distinct outcomes. We call this the number of permutation of \(n\) objects \(k\) at a time and write \(P(n,k)\).

You reach in pull out seven balls at a time.

Photo by Jopwell x PGA on Pexels.com

We again want to look like what makes results distinct. Here we will have that a pull is the same if exactly the same 7 balls are chosen. In this situation the ordering of the balls doesn’t matter, because they were all pulled at the same time. Also, we cannot have repeated outcomes because we were not able to replace the balls since all were taken out at the same time.

Instead of counting the total number of outcomes directly, we will instead look at the total outcomes if the order of the pull did matter, then count the number of such pulls that would now be considered the same pull so that we can reduce the number.

In the previous problem we had already counted the number of outcomes when order did matter, so we now just need to determine how many of these will now be considered the same. Therefore, suppose that we have chosen our 7 balls.

The outcome we have chosen will be equivalent to another choice if we can rearrange the balls so they correspond. Therefore, for each rearrangement of our outcome, we will have an over counting of outcomes in are current method.

If we look at this case, we now have 7 balls to choose from, and we need to arrange all 7 of them. Note that, we are now in the situation described in the last example, except we have to choose 7 balls from 7 total instead of 30 total. Therefore, the total number of rearrangements will be \(P(7,7)=7! =5040\).

This tells us that each unique outcome for our situation was counted 5040 times instead of just once. We can now find the distinct outcomes by taking the total number of permutations and dividing by the over-counting. Therefore, we will have \(P(30,7)/P(7,7) \approx 2\) million distinct outcomes.

In order to generalize this case, we will look at the situation where you choose k objects from n total possible. As you make this choice, repetition of results is not allowed and the order of the choices don’t matter. If this is the case, we will have that the total number of distinct outcomes are the number of permutations of k objects from n divided by the number of permutations of k object from k possible. We call this the number of combinations of n objects k at a time and denote that by \(\binom{n}{k}=P(n,k)/P(k,k)=\frac{n!}{(n-k)!k!}\).

Suppose that instead of being numbered, the balls are colored white, yellow and red, with 10 of each. You now reach in and pull out 7 at a time. How many distinct outcomes will there be?

In this case, we again want to decide what will make two different pulls distinct. Because we are pulling them all out at the same time, we note that order won’t matter. Therefore, two pulls will be distinct if there number of white balls, the number of yellow balls or the number of red balls in each pull is different. Since there are multiple white, yellow and red balls, we note that this will allow for repetition of balls in our answer since these are indistinguishable. As we try to count the number of balls, we will begin by looking at a sample outcome,
Note that this would be the same as the outcomes
In order to imagine comparing results, we could rearrange the balls to provide a direct comparison. In this way, we could put the white balls first, followed by the yellow balls then the red balls as we fill in the seven spots for the balls. Therefore, we could relabel the above results leaving out colors and get
In the above, we note that we will have two white balls, since white comes first, three yellow balls, since yellow comes second, and two red balls, since red is third. As we look at the result this way, we note that we only need to know where the black bars go in order to determine each distinct result. Because there are seven balls and two bars, this means that we need to choose the location for the two bars among the seven available spots. Now, we are left one a problem similar to what we’ve seen before. Note that we can’t have both bars in the same spot, so we cannot repeat choices. However, the order in which we choose the spots for the bars doesn’t matter because choosing, say, the first and third spot would result in the same outcome as choosing the third and first. In this way, we must choose 2 of the 9 spots. Therefore, the number of ways we can do this is \begin{align*} \binom{9}{2} =\frac{9!}{2!*7!}=36. \end{align*} As we generalize this, we must note that our choices depended on the fact that you could repeat each option for all outcomes. If this was not the case, we would need to change our approach. However, as is, we noted that we had 3 distinct options for each ball which led to two bars. These options could be repeated and the order did not matter. If we now assume that there are \(n\) choices for each individual outcome and we pick \(k\) individual outcomes, then the to count the total number of outcomes we will need to place \(n-1\) bars in \(k+n-1\) slots. That is, the total number of outcomes will be \begin{align*} \binom{k+n-1}{n-1}=\frac{(k+n-1)!}{(n-1)!k!}. \end{align*}

Conclusion

In each of these cases, we were taking 7 balls out of a bag of 30 distinct balls. When doing so, we need to determine if order mattered and if repetition of results was allowed. If order mattered and repetition was allowed, we found, in general that there would be \(n^{k}\) distinct outcomes. If order mattered, but repetition was not allowed, we had \(P(n,k)=\frac{n!}{(n-k)!}\) distinct outcomes. Then, if repetition was not allowed and order did not matter, then we had \(\binom{n}{k}= \frac{n!}{(n-k)!k!} \) distinct outcomes. As a final case, if order does not matter and repetition is allowed, then we will have \(\binom{k+n-1}{n-1}\) distinct outcomes, where \(n\) is the number of options in each individual choice and \(k\) is the number of times we choose.

I hope you learned something and found the post helpful. If you did, please like the post and share it with anyone else you might think will need some help with combinatorics.

1 thought on “Counting Balls”

We'd love to hear your thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.