# Counting, Permutations and Combinations

In What is most interesting; question, answer, or explanation? we discussed the idea that by studying a question and answer to determine why something is true can lead you to many exciting discoveries.  Often these discoveries are not where you thought you would end up, which makes the process even more exciting.  To further this discussion, I stated that I would like to go through this process of showing why the power rule, works for derivatives.  Today, we begin that discussion.

Before we get to the power rule, we will need some background information.  For example, we should know what a derivative is before we try to find one.  Even before we get here, however, we will need to learn to do some counting.

### Counting

Suppose that we have a standard deck of cards.  In a standard deck, there are 52 cards made of 4 suits with 13 numbers in each suit (including ace, jack, queen and king as numbers).  If we were to choose one card from the deck, how many ways can we do this?  Well, we’ve just seen that there are 52 cards, so there are 52 distinct ways to do this.  Viewed another way, however, we see that we can choose this card by picking one of the 4 suits, then deciding the number of the card.  In this case, if we want the total number of choices, we would take 4*13, which is, again, 52.

Now let’s suppose we want to pull 2 cards out of the deck.  How many possibilities are now available?  In this case, we have some ambiguity.  That is, do I care which card comes first, or don’t I?  Does it even make a difference?  Let’s look at this.

If the order matters, note that what we do is we choose a first card, for which we will have 52 options.  When we pick the second card, however, we will only have 51 cards left to choose from because the first card has already been drawn and placed down.  Therefore, the total number of ways to do this is 52*51.

On the other hand, if we dealt both at the same time, we wouldn’t be able to tell which one was first and which one was second.  Notice above that we counted a 5 of hearts followed by a 3 of clubs as a different outcome.  We now want this to be counted as one outcome.  Here, what we can do is look at the number of ways we found in order, but try to find out how much over counting there was.  Note that for any choice of 2 cards, when counting in order, we get 2 options, but when not counting we only have one.  Hence, we can find the number of ways to pick 2 cards at the same time by taking our previous result and dividing by 2.

If we continue to 3 cards, we note that there are 52*51*50 ways to deal the cards in order.  If we count this way, for every triplet of cards, we are counting different outcomes for each ordering of these three cards.  Therefore, how many ways can we order 3 cards?  Well that is 3*2*1 since we will have 3 choices for the first card, 2 for the second and 1 for the last.  Hence, the over-counting that occurred in our first technique compared to when order does not matter is 6.

In order to help with notation, we will write that n factorial is Using this notation, we saw that the number of ways to order 2 cards was 2! and the number of ways to order 3 cards was 3!.  In general, if we have n-elements and we want to place all n of them in order, the number of ways we can do this is precisely n! because we have n options for the first choice, n-1 for the second and so on down to the last choice having only 1 option.

Now, if I don’t order all of them, as was the case with my cards, we see that we will stop making choices before getting down to 1, so we will have fewer than n! options.  We saw that when choosing 3 cards we had 52*51*50, so we only took the product of the first three terms in 52!  In the same way, if we have n objects to choose from and we put k of them in order, we have that the total number of permutations of n objects k at a time is, Now, if order didn’t matter, than we saw that the above method resulted in an over-counting.  The amount of over-counting was precisely the number of ways we could reorder the k objects that we chose.  Therefore, we have that, the number of combinations of n objects k at a time (or n choose k) is, Many of you may have known this and I could have just given you these results.  However, I want to take the time to explore why we get these results when counting.  That is I wanted to look at; what are permutations (combinations) and why do we have as many as we do?

### Conclusion and notes

I wanted to make a note here that I haven’t provided a formal proof.  Rather I tried to use examples to show a pattern that the students can believe will continue.  As a mathematician, I would like it if a few of the above statements were even further clarified; however, I wanted to focus on the approach I would use if I presented this in a calculus class.  Therefore, I am trying to provide explanation, detail and justification, but I also don’t want to present anything above their general level of understanding.

I should also point out that since counting isn’t in the required material for calculus, I have not been able to work this into a calculus class itself.  I have; however, taught this in classes such as applied mathematics, finite mathematics, or other classes which considered to be at a lower level of calculus, and it has gone very well.

While it doesn’t seem that this has anything to do with the power rule for derivatives, we are indeed working to that end goal.  Part of the beauty of exploring why something is true is that you tend to explore topics you would never expect to be connected.  Therefore, you can use a topic to provide motivation to student without having to focus on the topic of the day.

In my next post, I will use these techniques to get closer to the power rule by showing that the binomial theorem is true.  Make sure to follow the blog so you can get updated when this is available.  Also, share with your friends so that you can go on this journey of knowledge together.

## 4 thoughts on “Counting, Permutations and Combinations”

1. Pingback: Binomial Theorem
2. Pingback: Power Rule

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