Question

What is a permutation calculation calculating?

Answer 1

it's a calculation that shows the number of ways a group can be picked if we care what the order of those picks is (like the way election results for student government can go).

Explanation:

Let's say we have a student government and there are 4 seats to be filled - the President, the Vice President, the Treasurer, and the Secretary. Let's also say there are 4 people running for those seats. How many different ways are there for those 4 people to hold those 4 positions?

We can look at see that for the President's seat, there are 4 candidates.

We can then look at the VP's seat and see that, with someone in the role of President, there are now 3 people left who can be VP.

Then we look to the Treasurer and see there are 2 people left.

And lastly there is the Secretary and the remaining person goes there.

Therefore there are: `4xx3xx2xx1= 4! =24` ways the election results can go.

This is an example of a factoral problem - we're going to take a population and take all the members of that population and place them (whether it's political office or movie seats or whatever - we're using the entire population).

What happens if we have more population than we have seats or places? For example, there are 6 people who are vying for those 4 government slots?

We could do it this way:

We can look at see that for the President's seat, there are 6 candidates.

We can then look at the VP's seat and see that, with someone in the role of President, there are now 5 people left who can be VP.

Then we look to the Treasurer and see there are 4 people left.

And lastly there is the Secretary and there are 3 remaining people who could go there.

So we get `6xx5xx4xx3=30xx12=360` ways to do this. But this is awkward to do all the time - especially if we have a large population and a large number of places that need filling (ex. A concert hall has 1,000 seats. What is the number of ways 5,000 fans can sit in those 1,000 seats). Wouldn't it be great if there were a formula that would make it easier to work with these types of calculations?

Notice that in the "6 people, 4 offices" example, we ended up with this calculation:

`6xx5xx4xx3`

How can we put that in terms of factorials? Well, if we multiply it by `2xx1` (and divide by that figure as well), we get:

`(6xx5xx4xx3xx2xx1)/(2xx1)`

And keep in mind that the definition of a factorial is that we multiply by each natural number up to and including the one with the sign (so `6! = 6xx5xx4xx3xx2xx1`), we can express this as:

`(6!)/(2!)`

And now see that the number 6 is the number of our population while 2 is the difference between the population and the number of seats that needed to be filled, `6-4=2`. So we can express this as:

`(6!)/((6-4)!)`

And that is exactly what the permutation formula is! If I call `n` the population and `k` the number I'm going to pick, we get:

`P_(n,k)=(n!)/((n-k)!)`

Lastly, I want to show that this formula still works if we have that initial example - 4 people running for 4 seats - we should get `4!`:

`P_(4,4)=(4!)/((4-4)!)=(4!)/(0!)=(4!)/1=4!`