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.**

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.**

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.**

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!}\).

**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.

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”