Permutations

Permutations of k elements from n different elements are all possible arrangements, that contain k elements, taken from n given elements. Arrangements differ from each other if they contain different elements, or order of elements is different. For example, abc, bac, acd are different arrangements.

In permutation ORDER is IMPORTANT!.

There are two forms of permutations:

  1. without repetitions - every element in the arrangement can occur only once (for example, permutations without repetitions from n=3 elements a,b,c of k=2 elements are following: ab,ba,ac,ca,bc,cb. Note that combination like aa is not allowed here).
  2. with repetitions - every element in the arrangement can occur more than once (for example, permutations with repetitions from n=3 elements a,b,c of k=2 elements are following: aa,bb,cc,ab,ba,ac,ca,bc,cb; permutations with repetitions from n=2 elements a,b of k=3 elements are aaa,aab,aba,abb,baa,bab,bba,bbb).

Number of permutations without repetitions of k elements from n elements is `P_n^k=(n!)/((n-k)!)=n(n-1)...(n-k+1)`, where `k<=n`.

`n!` is read as "n factorial" and it is product of all natural numbers from 1 to n: `n! =1*2*3*...*n`. For example, `6! =6*5*4*3*2*1=720`.

Note, that `0! =1`.

Number of permutations with repetitions of k elements from n elements is `bar(P)_n^k=n^k`.

Example 1. Football team consists of 11 players. How many ways are there to choose captain and vice captain?

First of all note that order is important here, because captain Bob and vice captain Paul is not same as captain Paul and vice captain Bob.

Also Bob can't be both captain and vice captain simultaneously, therefore we use formula for permutations without repetitions from n=11 elements of k=2 elements: `P_(11)^2=11*10=110`.

Example 2. How many 3-digit numbers can be formed from digits 1,2,3,4,5,6,7?

First of all note that order is important here, because 123 and 321 are different numbers.

Also digits can repeat, like in number 112, therefore we use formula for permutations with repetitions from n=7 elements of k=3 elements: `bar(P)_7^3=7^3=343`.