Permutations and Combinations

Suppose we have a set of five objects e.g.\ the set of letters A, B, C, D and E. Then these letters can be arranged in different permutations ABCDE, or DBCAE, or EACBD etc. Then we ask how many different permutations are there. The answer is that there are 5!\equiv 5.4.3.2.1 different permutations. For the first letter there are 5 possibilities, for the second only 4 because one has been used, for the third only 3 etc. The final answer is obtained by just multiplying these numbers.

The general result is that if we have n different objects then there are P_n=n!\equiv n.(n-1)\cdots 3.2.1 permutations. The factorial symbol n! is by convention given the value 1 when n=0 i.e. 0!=1

If we have n different objects and we choose m of them (with m < n of course) and ask how many different arrangements result then there are n.(n-1).\cdots (n-m+1) possibilities. This is called the number of permutations of n objects taken m at a time and written ^nP_m=n!/(n-m)!

If we have n different objects and we choose m of them (with m < n of course) and ask how many different choices we can make irrespective of order then we have to divide the previous result by the number of permutations of m objects i.e. by P_m=m!\,. This gives the number of combinations of n objects taken m at a time. This is written ^nC_m=n!/(n-m)!m! Note that ^nC_0=^nC_n=1.

A quick technique for deriving the ^nC_m\,\,'s is from Pascal's triangle.

\begin{eqnarray} \ &\ &\ &\ &1 &\ &1 &\ &\ &\ &\ \\ \ &\ &\ &1 &\ &2 &\ &1 &\ &\ &\ \\ \ &\ &1 &\ &3 &\ &3 &\ &1 &\ &\ \\ \ &1 &\ &4 &\ &6 &\ &4 &\ &1 &\ \\ 1 &\ &5 &\ &10&\ &10&\ &5 &\ &1 \end{eqnarray}

etc. where each row is formed from the one above by adding the two integers immediately above to the left and to the right. The combination ^nC_m is found by looking for the (m+1)-th number in the n-th row so ^5C_2 is found by looking for the third number in the fifth row i.e. 10.