Welcome to NRICH.

 
What's a permutation?
By Zhen Wah on January 27, 1999:

May I know what permutations are actually? There is a Binomial Theorem if I'm not wrong, right?

What actually is the Binomial Theorem?
Please explain this to me in a simple way, as I'm just a high school student now.

Has the Binomial Theorem got anything to do with combinations and permutations?

If yes, how? I'm asking this both for interest and for a Maths project.

Thanks for answering my question.

Thankfully,

zhen wah

By Simon Munday (sjm78) on January 28, 1999:

Permutations

Dear Zhen

Suppose you have a set of things that are in some order, for example the numbers 1, 2, 3, 4, and you change the order, say to 1, 3, 4, 2. What you have just done is called a permutation. A permutation is just a rearrangement. The set of things does not have to be finite, but permutations of infinite sets are usually dealt with separately and are known as bijections. I will only discuss permutations of finite sets.

The most important question we can ask about permutations is how many different permutations of a given set there are. Let's count the number of permutations of the set 1, 2, 3, 4. To start with, let's count how many different places the 1 could go to. It could stay where it is, or go to any on of the places initially occupied by the other three numbers. So that's four possibilities. Now for each of those four possibilities, there are three places left over, so we have three possibilities for the position of 2. After we've positioned 2 there are two places to choose between for the position of 3 and after that, there is no choice about where we put the last number, 4. So how many was that? It was 4x3x2x1 which we normally write 4! which is 24. In fact, if we have a set containing n different objects, e.g. 1, 2, 3,...., n-1, n there are n! = n(n-1)...2.1 permutations.

We also use the word permutation to mean something slightly different, which is a bit confusing (it wasn't my idea!). Instead of rearranging all the objects in the set, we choose to arrange a certain number of them. What we are doing here is choosing k of the n objects in our set in a certain order. Can you see that there are n(n-1)...(n-k+1) ways to do this? Count in the same way as before, asking how many ways there are to choose the first one, how many ways to choose the second, etc, up to the kth. Also notice that n(n-1)(n-2)...(n-k+1) = n!/k!.

Well done if you have followed this far! We can generalise again, and now we are getting close to the Binomial Theorem. What if we don't care about the order of the elements we choose from the set, and all we do care about is the number of different sets of k objects there are contained in our set of n objects. Perhaps we should go back to the example 1, 2, 3, 4. How many sets of two elements are there in this set. Well, there are three sets with 1 in, namely 1,2 , 1,3 and 1,4. These include a set with 2 in, so there are only two other sets with 2 in, namely 2,3 and 2,4. Now there is one set with 3 in that we haven't mentioned, which is 3,4 and now all the sets with 4 in have already been found. So there are 4 + 3 + 2 + 1 = 10 sets with two elements altogether. In general, we count the number of sets of size k in a set of size n by counting the number of ways of choosing k elements from a set of n elements (which is just the second sort of permutation) and dividing by the number of ways of permuting k things, because we are taking all sets containing the same k things in any order to be the same. This number, which from what I have said must be equal to n!/((n-k)!k!) is called a Binomial coefficient. It is written nCk and you say "n choose k".

Now we can discuss the Binomial Theorem. This says that

(x+y)n = nC0xny0 + nC1xn-1y1 + ...+ nCnx0yn.

Compare this with results you alreay know: does it give the right answer for n = 1 and n = 2? Well, for n = 1, there are only two terms on the right hand side (RHS) of the identity: 1C0x + 1C1y = x + y, so it works in that case. When n = 2 the RHS is 2C0x2 + 2C1xy + 2C2y2 = x2 +2xy +y2, which again is right. That's very reassuring, but why is the theorem true when n is any positive integer? You can think of it in terms of choosing a certain number of elements from sets of a certain size. If we write the LHS of the identity as (x+y)(x+y)...(x+y) we can think about "mulitplying out" as we would if there were only a few brackets. Each term on the RHS of the identity contains either an x or a y from each of the n brackets in this expression. So we can build up the term containing k y's and n-k x's, say, by counting the number of ways of choosing the k brackets to take the y's from. But this is just nCk, so there are nCk terms containing k y's and n-k y's and so that's where the RHS comes form. If that seems a bit difficult to follow, don't worry: the important thing is that you know the identity. Your calculator can probably work out the binomial coeffients for you, but I think it's nice to know where these things come from.

I hope you got to the end without giving up.