The Unapologetic Mathematician

Mathematics for the interested outsider

Permutations and Combinations

Okay, here’s a classic bit of combinatorics that I’m almost surprised I never mentioned before: how to count permutations and combinations.

Back when I defined permutation groups, I gave a quick argument about how to count their orders. That is, how many elements are in the group S_n. If we’re permuting the set of numbers 1 through n, first we have to choose where to send 1. There are n possible choices of how to do this. Then we have to choose where to send 2, which can be anywhere but the place we sent 1. Thus there are n-1 choices of how to do this. And so on we go, making n-2 choices of where to send 3, n-3 choices of where to send 4. And so in total we have n*(n-1)*(n-2)*...*3*2*1=n! permutations.

Notice that what we’ve really done there is picked out an ordering on the set \{1,...,n\}. More specifically, we’ve picked an ordering of the whole set. But what if we want to pick out only an ordered subset? That is, what if we want to pick out an ordered list of k numbers from the set with no repetitions? Well, since there’s only one order type for each finite cardinal number, let’s just pick one as the model for our ordered list. Specifically, we’ll use the numbers from 1 to k, in their usual order.

Now we’ll take an injective function from \{1,...,k\} to \{1,...,n\}. The image subset will be our list, and we carry over the order from \{1,...,k\} onto it. But now we can reuse the same argument as above! First we have n choices where to send 1, and then n-1 choices where to send 2, and so on until we have n-(k-1) choices of where to send k. So there are n*(n-1)*...*(n-k+2)*(n-k+1) such ordered subsets of length k. This gets called the number of permutations with k elements, and written as P(n,k), or {}_nP_k or P^n_k. Notice that when k=n this reduces to the factorial as above.

There’s an easy way to express this number in notation we already know. First we can multiply all the numbers from 1 to n, and then we can divide out the ones from 1 to n-k. That is, P(n,k)=\frac{n!}{(n-k)!}. What does this mean? Well, the n! up top means that we’re ordering all the elements of our set. But then since we only care about the first k we don’t care about the order on the last n-k elements. What’s hiding here is that the group S_{n-k} is secretly acting on the set of all permutations of our set by rearranging the last n-k elements of the permutation. What’s more, it acts freely — with no fixed points — so every orbit has the same size: (n-k)!. But since we only care about the first k places in the permutation, we’re really interested in the number of orbits. That is, the total number of permutations divided by the size of each orbit: \frac{n!}{(n-k)!}. And this is the formula we came up with before.

This is a general principle in combinatorics. It’s often possible to see the set you’re trying to count as a larger set modulo the free action of some group. Then the cardinality of the set you’re interested in is the cardinality of the larger set divided by the order of the group.

To see this in action, what if we don’t care about the order of our subset? That is, we just want to pick out k elements with no repetitions and no care about what order they come in. Well, first we can pick out an ordered set of k elements. Then we can use the group S_k to rearrange them. Any rearrangement is just as good as any other, and the group S_k acts freely on the set of permutations. That is, the number of unordered subsets is the number of ordered subsets — \frac{n!}{(n-k)!} — divided by the order of the group S_kk!. This number of unordered subsets we call the number of “combinations” of an n element set with k elements. This is often written as C(n,k), or {}_nC_k, or C^n_k, or \binom{n}{k}, and they all are given by the formula \frac{n!}{k!(n-k)!}.

About these ads

December 29, 2008 - Posted by | Combinatorics

6 Comments »

  1. [...] of subsets of the basis for . There are basis vectors overall, and we must pick of them. But we know how to count these. This is a number of [...]

    Pingback by Dimensions of Symmetric and Antisymmetric Tensor Spaces « The Unapologetic Mathematician | December 30, 2008 | Reply

  2. [...] one of the indices we don’t take the . Incidentally, we could also think of this in terms of combinations, as [...]

    Pingback by The Trace of a Linear Transformation « The Unapologetic Mathematician | January 30, 2009 | Reply

  3. pls I need all the possible outcome of 90 combination 5.
    thus nCr = 90C5.
    or in what manner or solfware help can i get such outcome?

    Comment by Adebayo S.T | February 5, 2010 | Reply

  4. Five students from the 90 students in your clss not running for class president will be selected to count the ballots for the vote for class president. In how many ways can the 5 students be selected?

    Comment by tracy | March 2, 2010 | Reply

  5. Twenty students are dunning for 3 different positions on student council. In how many ways can the 3 positions be filled?

    Comment by tracy | March 2, 2010 | Reply

  6. tracy, are you asking me to do your homework?

    Comment by John Armstrong | March 2, 2010 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 391 other followers

%d bloggers like this: